# Matchings in multipartite hypergraphs

Candida Bowtell  Mathematics Institute, Zeeman Building, University of
Warwick, Coventry CV4 7AL, United Kingdom<EMAIL_ADDRESS>and
Richard Mycroft  School of Mathematics, University of Birmingham, Birmingham
B15 2TT, United Kingdom<EMAIL_ADDRESS>
###### Abstract.

A folklore result on matchings in graphs states that if $G$ is a bipartite
graph whose vertex classes $A$ and $B$ each have size $n$, with $\deg(u)\geq
a$ for every $u\in A$ and $\deg(v)\geq b$ for every $v\in B$, then $G$ admits
a matching of size $\min\\{n,a+b\\}$. In this paper we establish the analogous
result for large $k$-partite $k$-uniform hypergraphs, answering a question of
Han, Zang and Zhao, who previously demonstrated that this result holds under
the additional condition that the minimum degrees into at least two of the
vertex classes are large. A key part of our proof is a study of rainbow
matchings under a combination of degree and multiplicity conditions, which may
be of independent interest.

CB gratefully acknowledges support from ERC Advanced Grant 883810, ERC
Starting Grant 947978 and Philip Leverhulme Prize PLP–2020–183; RM gratefully
acknowledges support from EPSRC Standard Grant EP/R034389/1.

##  1\. Introduction

An old folklore result, whose proof often appears as a straightforward
exercise in elementary graph theory courses, states the following.

######  Fact 1.1.

Let $G$ be a bipartite graph whose vertex classes $A$ and $B$ contain $n$
vertices each. If $\deg(u)\geq a$ for every vertex $u\in A$, and $\deg(v)\geq
b$ for every vertex $v\in B$, then $G$ admits a matching (i.e. a set of
pairwise-disjoint edges) of size $\min\\{n,a+b\\}$.

This bound on the size of the matching is best possible for all $a,b$ and $n$,
in the sense that it is not possible to have a matching of size larger than
$n$, and moreover there exist graphs satisfying the degree conditions which do
not contain a matching of size larger than $a+b$.

The central result of this paper is to prove the analogous statement for large
multipartite hypergraphs. To explain this precisely, we make the following
definitions, all of which are standard in extremal graph theory. A _$k$
-uniform hypergraph_, or simply _$k$ -graph_, consists of a vertex set $V$ and
an edge set $E$, where each edge is a set of $k$ vertices. So, in particular,
a $2$-graph is a simple graph. Exactly as for graphs, a _matching_ in a
$k$-graph $H$ is a set of pairwise-disjoint edges, and we write $\nu(H)$ for
the _matching number_ of $H$, that is, the size of a largest matching in $H$.
A matching in $H$ is _perfect_ if it covers every vertex of $H$. We say that a
$k$-graph is _$k$ -partite_ if its vertex set $V$ admits a partition
$V=V_{1}\cup\dots\cup V_{k}$ for which every edge $e\in E$ has precisely one
vertex in each set $V_{i}$; we refer to the sets $V_{i}$ as _vertex classes_.
Observe that a $2$-partite $2$-graph is exactly a bipartite graph. Given a
$k$-partite $k$-graph $H$ with vertex classes $V_{1},\ldots,V_{k}$, we say
that a set $S\subseteq V(H)$ is _crossing_ if it has at most one vertex in
each vertex class, and that $S$ _avoids_ $V_{i}$ if $S\cap V_{i}=\emptyset$.
For a crossing $(k-1)$-tuple $S$ of vertices of $V(H)$, we define the _degree_
$\deg(S)$ of $S$ to be the number of edges $e\in E(H)$ with $S\subseteq e$ (in
other words, the number of ways to add a vertex to $S$ to form an edge of $H$;
note that since $H$ is $k$-partite this vertex must come from the vertex class
which $S$ avoids). Finally, for each $i\in[k]$ we define the _minimum
multipartite codegree into $V_{i}$_, denoted
$\delta_{[k]\setminus\\{i\\}}(H)$, to be the minimum of $\deg(S)$ over all
crossing $(k-1)$-tuples $S$ of vertices of $H$ which avoid $V_{i}$. We can now
give the statement of our main result.

######  Theorem 1.2.

For each $k\geq 3$, there exists $n_{0}$ for which the following statement
holds. Let $H$ be a $k$-partite $k$-graph with vertex classes
$V_{1},\dots,V_{k}$ each of size $n\geq n_{0}$ in which
$\delta_{[k]\setminus\\{i\\}}(H)\geq a_{i}$ for each $i\in[k]$. Then

$\nu(H)\geq\min\\{n-1,\sum_{i=1}^{k}a_{i}\\}.$

One might initially wonder whether we could hope for the stronger conclusion
that $\nu(H)\geq\min\\{n,\sum_{i\in[k]}a_{i}\\}$ in Theorem 1.2. However,
Theorem 1.2 was shown to be best possible in this sense by the following
extremal construction presented by Han, Zang and Zhao [17].

######  Example 1.3 (Divisibility barrier).

Take sets $V_{i}:=A_{i}\dot{\cup}B_{i}$ with $n/2-1\leq|A_{i}|\leq n/2+1$ for
each $i\in[k]$, ensuring that $\sum_{i\in[k]}|A_{i}|$ is odd. Let $H$ be the
$k$-partite $k$-graph with vertex classes $V_{1},\dots,V_{k}$ whose edges are
all crossing $k$-tuples containing an even number of vertices in
$\bigcup_{i\in[k]}A_{i}$. We then have $\delta_{[k]\setminus\\{i\\}}(H)\geq
a_{i}:=n/2-1$ for each $i$, so $\sum_{i\in[k]}a_{i}\geq k(n/2-1)$. However,
every matching $M$ in $H$ contains an even number of vertices in
$\bigcup_{i\in[k]}A_{i}$, so is not perfect since $\sum_{i\in[k]}|A_{i}|$ is
odd.

The same authors also presented the following extremal construction showing
that the conclusion of Theorem 1.2 cannot be strengthened in the case when
$\sum_{i\in[k]}a_{i}\leq n-1$.

######  Example 1.4 (Space barrier).

Take sets $A_{i}\subseteq V_{i}$ with $|A_{i}|=a_{i}$ and $|V_{i}|=n$ for each
$i\in[k]$, and let $H$ be the $k$-partite $k$-graph with vertex classes
$V_{1},\dots,V_{k}$ whose edges are all crossing $k$-tuples which intersect
$\bigcup_{i\in[k]}A_{i}$. We then have $\delta_{[k]\setminus\\{i\\}}(H)\geq
a_{i}$ for each $i\in[k]$, but every matching $M$ in $H$ then has
$|M|\leq|\bigcup_{i\in[k]}A_{i}|=\sum_{i\in[k]}a_{i}$ since every edge of $M$
contains a vertex from $\bigcup_{i\in[k]}A_{i}$.

Previous work on this question established many cases of Theorem 1.2. Indeed,
Han, Zang and Zhao [17] observed that Theorem 1.2 may be proved in the case
when $\sum_{i\in[k]}a_{i}\leq n-k+2$ by adapting a short elegant argument of
Kühn and Osthus [25] which gave a matching of size $n-k+2$ in the case in
which $a_{i}=n/k$ for each $i\in[k]$ by showing that any smaller matching can
be enlarged by removing an edge and adding two new edges.

######  Fact 1.5.

Let $H$ be a $k$-partite $k$-graph with vertex classes $V_{1},\dots,V_{k}$
each of size $n$. If $\delta_{[k]\setminus\\{i\\}}(H)\geq a_{i}$ for every
$i\in[k]$, then

$\nu(H)\geq\min\\{n-k+2,\sum_{i=1}^{k}a_{i}\\}.$

In the same paper, Han, Zang and Zhao used a sophisticated absorbing argument
to prove Theorem 1.2 in all cases where at least two of the minimum
multipartite codegrees are large.

######  Theorem 1.6.

[17, Theorem 1.1] For each $k\geq 3$ and all $\varepsilon>0$ there exists
$n_{0}\in\mathbb{N}$ for which the following statement holds. Let $H$ be a
$k$-partite $k$-graph with vertex classes $V_{1},\dots,V_{k}$ each of size
$n\geq n_{0}$ in which $\delta_{[k]\setminus\\{i\\}}(H)\geq a_{i}$ for each
$i\in[k]$. If $a_{1}\geq a_{2}\geq\ldots\geq a_{k}$ and $a_{2}>\varepsilon n$,
then

$\nu(H)\geq\min\\{n-1,\sum_{i=1}^{k}a_{i}\\}.$

It remained to establish Theorem 1.2 in the cases where all but one of the
minimum multipartite codegrees are small, and Han, Zang and Zhao remarked that
they were not sure whether the statement extends to the remaining cases. In
this paper we show that this is indeed the case, and in fact we obtain a
slightly stronger bound in the remaining cases, as stated in the following
theorem.

######  Theorem 1.7.

For each $k\geq 3$ there exists $n_{0}\in\mathbb{N}$ for which the following
statement holds. Let $H$ be a $k$-partite $k$-graph with vertex classes
$V_{1},\dots,V_{k}$ each of size $n\geq n_{0}$ in which
$\delta_{[k]\setminus\\{i\\}}(H)\geq a_{i}$ for each $i\in[k]$. If $a_{1}\geq
a_{2}\geq\ldots\geq a_{k}$ and $\sum_{i\in[2,k]}a_{i}\leq\frac{n}{1600k^{4}}$,
then

$\nu(H)\geq\min\\{n,\sum_{i=1}^{k}a_{i}\\}.$

Taking $\varepsilon=1/1600k^{5}$, Theorems 1.6 and 1.7 together prove Theorem
1.2, since by relabelling the vertex classes if necessary we may assume
without loss of generality that $a_{1}\geq a_{2}\geq\ldots\geq a_{k}$.

###  1.1. Wider context

Determining the size of a largest matching in a given $k$-graph is a key
question in extremal combinatorics which has been a central focus of research
activity over recent decades. As well as being a natural, fundamental question
in its own right, this question arises since matchings provide a general
framework for many important problems within combinatorics such as
combinatorial designs, Latin squares, tilings and decompositions, as well as
in practical applications such as the ‘Santa Claus’ allocation problem [4] and
for distributed storage allocation [3]. In the graph case Edmond’s blossom
algorithm [10] gives an efficient method for computing a largest matching,
whilst Hall’s marriage theorem [11] and Tutte’s theorem [39] give elegant
characterisations of bipartite graphs and arbitrary graphs respectively which
contain perfect matchings. By contrast, for $k\geq 3$ the problem of
determining the size of a largest matching in a $k$-graph is an NP-hard
problem, as is the more restricted question of whether a given 3-partite
3-graph contains a perfect matching; the latter problem is often referred to
as _3-dimensional matching_ and was one of Karp’s original 21 NP-complete
problems [19]. Consequently we do not expect to find similar characterisations
as for the graph case. Instead, the principal direction of research has been
to identify sufficient conditions which guarantee the existence of a matching
of size $s$ in a $k$-graph $H$, with particular focus on the case of a perfect
matching, i.e. when $s=|V(H)|/k$. Since a necessary condition for a perfect
matching is that $H$ has no isolated vertices, the most natural parameters to
consider are minimum degree conditions, also known as Dirac-type conditions
after Dirac’s celebrated theorem [9] that every graph $G$ on $n\geq 3$
vertices with minimum degree $\delta(G)\geq n/2$ contains a Hamilton cycle (a
cycle covering every vertex); for even $n$, choosing every other edge from
such a cycle gives a perfect matching in $G$. (Another recent research focus
has been to find minimum degree conditions under which the perfect matching
problem in $k$-graphs is computationally tractable [13, 16, 20, 21, 37].)

The strongest and most frequently used minimum degree conditions for
$k$-uniform hypergraphs $H$ are _codegree_ conditions, that is, conditions on
the degree, $\deg(S)$, of sets $S\subseteq V(H)$ of size $k-1$; the usefulness
of such conditions is that for such sets $\deg(S)$ indicates the number of
vertices which can be added to $S$ to form an edge of $H$. Recall from the
opening section that for a $k$-partite $k$-graph $H$ with vertex classes
$V_{1},\dots,V_{k}$ the minimum multipartite codegree into $V_{i}$, denoted
$\delta_{[k]\setminus\\{i\\}}(H)$, is the minimum of $\deg(S)$ over all
crossing $(k-1)$-tuples which avoid $V_{i}$; in the same way we define the
minimum multipartite codegree of $H$, denoted $\delta^{*}_{k-1}(H)$, to be the
minimum of $\deg(S)$ over all crossing $(k-1)$-tuples. For general (i.e. not
necessarily $k$-partite) $k$-graphs $H$ we likewise define the _minimum
codegree of $H$_, denoted $\delta_{k-1}(H)$, to be the minimum of $\deg(S)$
over all sets of $k-1$ vertices.

Kühn and Osthus [25] gave asymptotically best-possible sufficient minimum
codegree conditions for a perfect matching in both settings, specifically
$\delta^{*}_{k-1}(H)>n/2+O(\sqrt{n\log(n)})$ in the multipartite setting (with
$n$ being the common size of the vertex classes) and
$\delta_{k-1}(H)>n/2+O(\sqrt{n\log(n)})$ in the non-partite setting (where
$n=|V(H)|$ and we assume the necessary condition that $k$ divides $n$ without
further comment). For the general setting Rödl, Ruciński and Szemerédi [35]
improved this result to the exact best-possible minimum codegree condition for
large values of $n$, namely $\delta_{k-1}(H)\geq n/2-k+c$ where
$c\in\\{1/2,1,3/2,2\\}$ depends on the values of $n$ and $k$. Similarly, in
the multipartite setting Aharoni, Georgakopoulos and Sprüssel [1] showed that
(for large $n$) if $H$ is a $k$-partite $k$-graph such that
$\delta_{[k]\setminus\\{1\\}}(H)>n/2$ and $\delta_{[k]\setminus\\{2\\}}(H)\geq
n/2$, then (with no further conditions on the minimum multipartite codegree
into parts $V_{3},\ldots,V_{k}$) $H$ must contain a perfect matching; in
particular this implies that the condition $\delta^{*}_{k-1}(H)>n/2$ is a
best-possible sufficient condition for the existence of a perfect matching in
$H$.

Turning now to smaller (i.e. non-perfect) matchings, Kühn and Osthus [25] gave
a short elegant argument considering the size of a largest matching to show
that if $H$ is a $k$-partite $k$-graph with vertex classes each of size $n$,
and $\delta^{*}_{k-1}(H)\geq n/k$, then $H$ contains a matching of size
$n-k+2$. It follows immediately from their argument that for $s\leq n-k+2$, if
$\delta^{*}_{k-1}(H)\geq\lceil{s/k}\rceil$ then $H$ contains a matching of
size $s$. Rödl, Ruciński and Szemerédi [35] adapted this argument to the
general setting, showing that for $s\leq\lfloor{n/k}\rfloor-k+2$ every
$k$-graph $H$ with $\delta_{k-1}(H)\geq s$ has a matching of size $s$. These
results left open the correct condition for a matching of size $s$ in the
cases $n-k+3\leq s<n$ (in the multipartite setting) or size
$\lfloor{n/k}\rfloor-k+3\leq s<n/k$ (in the general setting). For the general
setting this question was answered asymptotically by Rödl, Ruciński and
Szemerédi [36] before Han [12] gave an exact answer for large $n$, showing
that $\delta_{k-1}(H)\geq s$ is a best-possible sufficient condition for these
cases also. In the multipartite setting Rödl and Ruciński [34, Problem 3.14]
asked, for a $k$-partite $k$-graph $H$ with vertex classes each of size $n$,
whether the condition $\delta^{*}_{k-1}(H)\geq\lceil n/k\rceil$ was sufficient
for a matching of size $n-1$, and this was answered in the affirmative by Lu,
Wang and Yu [30] and independently by Han, Zang and Zhao [17]; the latter
authors also showed that $\delta^{*}_{k-1}(H)\geq\lfloor n/k\rfloor$ suffices
in the case where $n\equiv 1\mod k$. This established the correct condition
for $s=n-1$, and the correct condition for the remaining values of $s$, namely
that $\delta^{*}_{k-1}(H)\geq\lceil s/k\rceil$ is a best-possible sufficient
condition, follows immediately from the proof given by Han, Zang and Zhao.
Note that Theorem 1.2 gives a wide-ranging generalisation of these
multipartite results by giving a much broader collection of codegree
conditions which ensure the existence of a matching of size $n-1$.

Given a $k$-graph $H$ it is also natural to consider conditions on the degree,
$\deg(T)$, of sets $T\subseteq V(H)$ of fewer than $k-1$ vertices (which is
again defined to be the number of edges containing $T$). For each $1\leq t\leq
k-1$ we define the _minimum $t$-degree_ of $H$, denoted $\delta_{t}(H)$, to be
the minimum of $\deg(T)$ over all sets $T\subseteq V(H)$ of size $t$; in
particular $\delta_{1}(H)$ is also commonly referred to as the minimum vertex
degree of $H$. Much work [3, 5, 6, 7, 8, 18, 14, 23, 24, 27, 28, 31, 32, 38]
has focused on identifying best-possible conditions on $\delta_{t}(H)$ which
suffice to ensure the existence of a perfect matching (or a matching of a
given size $s$) in $H$ for $t\leq k-2$, however for $t<0.42k$ the problem
remains open in general.

Turning back to the multipartite setting in which $H$ is a $k$-partite
$k$-graph whose vertex classes each have size $n$, for the case $k=3$, Lo and
Markström [29] gave the exact best-possible minimum vertex degree condition to
ensure a perfect matching in a $3$-partite $3$-graph for sufficiently large
$n$, as well as the exact best-possible minimum vertex degree condition to
ensure a matching of size $m+1$ for every $m$ when $n\geq 3^{7}m$. Pikhurkho
instead considered an inhomogeneous type of degree condition, writing
$\delta_{I}(H):=\min\\{\deg(S):|S\cap V_{j}|=1\mbox{ if and only if }j\in
I\\}$ for each set $I\subseteq[k]$; he showed that if there exists
$\emptyset\neq L\subsetneq[k]$ with
$\frac{\delta_{L}(H)}{n^{k-|L|}}+\frac{\delta_{[k]\setminus
L}(H)}{n^{|L|}}=1+\Omega\left(\sqrt{\frac{\log(n)}{n}}\right)$ then $H$
contains a perfect matching. Keevash and Mycroft [22] (see also Han [15]) also
gave degree sequence conditions – where an edge may be constructed vertex-by-
vertex with a given number of options at each step – which suffice to ensure a
perfect matching in this setting.

We recommend the surveys of Kühn and Osthus [26], Rödl and Ruciński [34] and
Zhao [40] for further information on this and related problems.

###  1.2. Main ideas

As in Theorems 1.6 and 1.7, let $H$ be a $k$-partite $k$-graph with vertex
classes $V_{1},\dots,V_{k}$ each of size $n\geq n_{0}$ in which
$\delta_{[k]\setminus\\{i\\}}(H)\geq a_{i}$ for each $i\in[k]$, where
$a_{1}\geq a_{2}\geq\ldots\geq a_{k}$. At first glance it may seem surprising
that the cases of Theorem 1.2 which remained open are those in which
$a_{2},\dots,a_{k}$ are all small, since in light of Fact 1.5 we may then
assume that $a_{1}$ is very close to $n$, meaning that $H$ is extremely dense.
However, it is possible in this case that the condition that
$\delta_{[k]\setminus\\{1\\}}(H)\geq a_{1}$ is satisfied by the existence of a
set $S\subseteq V_{1}$ of size $a_{1}$ whose vertices form edges with all
crossing $(k-1)$-tuples which avoid $V_{1}$. This makes it trivial to find a
matching covering all vertices of $S$, but such a matching is still not large
enough to meet the requirement of Theorem 1.2. Consequently our matching must
also contain edges which do not intersect $S$, but the fact that
$a_{2},\dots,a_{k}$ are all small means that the $k$-graph formed by such
edges can be very sparse. For instance, if $a_{2},\dots,a_{k}$ are all of
constant size, then the number of such edges could be of order $O(n^{k-1})$.
The central difficulty in proving Theorem 1.7 is to construct a sufficiently
large matching in this sparse environment.

Rainbow matchings under a combination of degree and multiplicity. Most of the
work in proving Theorem 1.7 is contained in Section 2, where we consider large
rainbow matchings in families of $k$-partite $k$-graphs which satisfy a
combination of degree and multiplicity conditions. For this we make the
following definitions: let $\mathcal{H}:=\\{H_{1},\ldots,H_{t}\\}$ be a family
of $k$-graphs on the same vertex set $V$. A _rainbow matching_ in
$\mathcal{H}$ is a set $M$ of pairwise-disjoint $k$-tuples of vertices of $V$
such that there is an injective map $\phi:M\to[t]$ for which $e\in
E(H_{\phi(e)})$ for every $e\in M$. In other words, $M$ is a matching within
the union of the $k$-graphs in $\mathcal{H}$ in which each edge of $M$ is
taken from a distinct member of $\mathcal{H}$. Implicitly fixing such an
injection $\phi$, we say that the edge $e\in M$ has _colour_ $j$ if and only
if $\phi(e)=H_{j}$ (so the colour of $e$ is the unique $k$-graph in
$\mathcal{H}$ from which it is taken, not simply a $k$-graph in $\mathcal{H}$
which contains $e$, of which there may be many). We say that a rainbow
matching in $\mathcal{H}$ is _perfect_ if it has size $t$ (the size of
$\mathcal{H}$), meaning that $\mathcal{H}$ has precisely one edge of each
colour.

The scenario we work with in Section 2 is that we have a family
$\mathcal{H}=\\{H_{1},\ldots,H_{t}\\}$ of $k$-partite $k$-graphs on common
vertex classes $V_{1},\dots,V_{k}$ each of size $n$ which satisfies, for some
integers $a_{1},\dots,a_{k}$ and $m$, the conditions that

  1. (i)

for every $j\in[t]$ and $i\in[k]$ we have
$\delta_{[k]\setminus\\{i\\}}(H_{j})\geq a_{i}$, and

  2. (ii)

every crossing $k$-tuple of vertices is an edge of at least $m$ of the
$k$-graphs in $\mathcal{H}$.

We describe in the next subsection how such a family arises naturally in the
context of Theorem 1.7 as a collection of link graphs of vertices in the first
vertex class of $H$. The key parameters we work with are $m$ and
$q:=\sum_{i\in[k]}a_{i}$. Indeed, the key step in the proof of Theorem 1.7 is
Lemma 2.5, which states that — provided $m$ is small relative to $q$, and
assuming the necessary condition that $t\geq m+q$ — conditions (i) and (ii)
are sufficient to guarantee a rainbow matching in $\mathcal{H}$ of size $m+q$
(for $n$ sufficiently large).

Whilst this result is sufficient for our purposes in this paper, we suggest
that conditions (i) and (ii) should in fact guarantee a rainbow matching of
size $m+q$ for a much wider range of values of $m$ and $q$; given the natural
way in which conditions (i) and (ii) arise (described below) we hope that this
question may be of independent interest. On the other hand, we cannot hope for
these conditions to ensure a rainbow matching of size larger than $m+q$; to
see this, let $H_{1},\dots,H_{m}$ be complete $k$-partite $k$-graphs, whilst
$H_{m+1},\dots,H_{t}$ are as in Example 1.4. We then have no rainbow matching
in $\mathcal{H}$ with size larger than $m+q$, since no rainbow matching in
$\\{H_{m+1},\dots,H_{t}\\}$ has size larger than $\sum_{i\in[k]}a_{i}=q$.

For $m=0$ (meaning that condition (ii) provides no information) and $q\geq t$
Pokrovskiy [personal communication] gave an elegant induction argument to show
that a perfect rainbow matching (i.e. of size $t$) must exist; this argument
was the inspiration for our Lemma 2.2, and we include it here for completeness
(though we do not use it in our proof). For a $k$-graph $H$ we say that a set
$U\subseteq V(H)$ is a dominating set if $U\cap e\neq\emptyset$ for every
$e\in E(H)$.

######  Lemma 1.8.

Let $V_{1},V_{2},\dots,V_{k}$ be disjoint sets of vertices, and let
$\mathcal{H}:=\\{H_{1},\ldots,H_{t}\\}$ be a family of $k$-partite $k$-graphs
each with vertex classes $V_{1},\ldots,V_{k}$ such that for every $i\in[k]$
and $j\in[t]$ we have $\delta_{[k]\setminus\\{i\\}}(H_{j})\geq a_{i}$. If
$t\leq\sum_{i=1}^{k}a_{i}\leq\frac{\min_{i\in[k]}|V_{i}|}{k^{10}}$, then
$\mathcal{H}$ has a perfect rainbow matching.

###### Proof.

We proceed by induction on $t$; the case $t=0$ is trivial, so suppose that the
lemma holds for families of size $t-1$. Without loss of generality, we may
assume that $t=\sum_{i=1}^{k}a_{i}$ and that $a_{1}\geq\frac{t}{k}$.

Case 1: $H_{t}$ contains a matching $M$ of size $kt-k+1$. By induction applied
to $\mathcal{H^{\prime}}=\\{H_{1},\ldots,H_{t-1}\\}$, the family
$\mathcal{H}^{\prime}$ admits a rainbow matching $M^{\prime}$ of size $t-1$.
Since $M$ has size $kt-k+1$ and $|V(M^{\prime})|=k(t-1)$, there must exist an
edge $e\in M$ with $e\cap V(M^{\prime})=\emptyset$, and then
$M^{\prime}\cup\\{e\\}$ is a rainbow matching for
$\mathcal{H}=\\{H_{1},\ldots,H_{t}\\}$ of size $t$, as required.

Case 2: $H_{t}$ contains no matching $M$ of size $kt-k+1$. It follows that the
vertex set of a maximum matching in $H_{t}$ is a dominating set $D$ of order
strictly less than $k^{2}t$. Let $e_{1},\ldots,e_{k^{5}t}$ be an arbitrary
family of pairwise-disjoint crossing $(k-1)$-tuples avoiding $V_{1}$ which do
not intersect $D$. This is possible since $D$ intersects each $V_{i}$ in at
most $kt$ vertices and $|V_{i}|-kt\geq k^{10}t-kt\geq k^{5}t$ for each
$i\in[k]$. The degree condition implies that for each $j\in[k^{5}t]$ the
$(k-1)$-tuple $e_{j}$ has at least $a_{1}$ neighbours in $H_{t}$ (that is,
$|N_{H_{t}}(e_{j})|\geq a_{1}$). Since every edge in $H_{t}$ intersects $D$,
and $e_{j}$ is disjoint from $D$, we have $N_{H_{t}}(e_{j})\subseteq D$ for
each $j\in[k^{5}t]$. So by averaging, some vertex $v\in V_{1}$ is a neighbour
of at least $k^{5}ta_{1}/|D|\geq k^{2}t$ of the $(k-1)$-tuples $e_{j}$, where
the inequality holds since $a_{1}\geq t/k$ and $|D|\leq k^{2}t$. By
relabelling the $e_{j}$ if necessary we may assume that
$v\in\bigcap_{j\in[k^{2}t]}N_{H_{t}}(e_{j})$. Let
$V^{\prime}=\bigcup_{i\in[k]}V_{i}\setminus\\{v\\}$ and let
$H^{\prime}_{j}=H_{j}[V^{\prime}]$ for each $j\in[t-1]$; by induction the
family $\mathcal{H^{\prime}}=\\{H^{\prime}_{1},\ldots,H^{\prime}_{t-1}\\}$
then admits a rainbow matching $N$ of size $t-1$ which, by construction, does
not cover the vertex $v$. Furthermore, $|V(N)|=k(t-1)<k^{2}t$ and so there
exists $j\in[k^{2}t]$ for which $e_{j}\cap V(N)=\emptyset$. It follows that
$M=N\cup\\{\\{v\\}\cup e_{j}\\}$ is a rainbow matching for
$\mathcal{H}=\\{H_{1},\ldots,H_{t}\\}$ of size $t$, as required. ∎

Outline proof of Theorem 1.7. To illustrate how the result for rainbow
matchings described above can be used to prove Theorem 1.7, we consider here
the the case of Theorem 1.7 in which $\sum_{i\in[k]}a_{i}=n$; the argument for
the other cases not covered by Fact 1.5 is broadly similar. In this case we
wish to find a perfect matching in $H$. Write $q:=\sum_{2\leq i\leq
k}a_{i}=n-a_{1}$, so the assumption of Theorem 1.7 implies that $q$ is small.
We choose an arbitrary perfect matching $M$ in the complete $k$-partite
$k$-graph on $V_{2},\dots,V_{k}$, and use a double-counting argument
(Proposition 3.2) to show that there is a subset $X\subseteq V_{1}$ of size
close to $n-q$ such that every vertex in $X$ forms an edge with many
$(k-1)$-tuples in $M$. Let $Z=V_{1}\setminus X$ be the set of the remaining
vertices of $V_{1}$, so $|Z|$ is slightly larger than $q$.

For each vertex $v\in Z$ let $L_{v}(H)$ be the _link graph_ of $v$; this is
the $(k-1)$-partite $(k-1)$-graph with vertex classes $V_{2},\dots,V_{k}$
whose edges are all crossing $(k-1)$-tuples $f$ for which $\\{v\\}\cup f\in
E(H)$. The assumption that $\delta_{[k]\setminus\\{i\\}}(H)\geq a_{i}$ for
$i\in[2,k]$ yields a similar condition on the link graph $L_{v}(H)$ for each
$v\in Z$, namely that for each $i\in[2,k]$, each crossing $(k-2)$-tuple
avoiding $V_{i}$ has at least $a_{i}$ neighbours in $V_{i}$. Moreover, the
assumption that $\delta_{[k]\setminus\\{1\\}}(H)\geq a_{1}$ yields a
multiplicity condition on the link graphs $L_{v}(H)$, namely that every
crossing $(k-1)$-tuple $f$ avoiding $V_{1}$ appears in at least $a_{1}$ of the
link graphs $L_{v}(H)$ of vertices $v\in V_{1}$; it follows that $f$ appears
in at least $m:=|Z|-(n-a_{1})=|Z|-q$ of the link graphs $L_{v}(H)$ of vertices
$v\in Z$ (see Proposition 3.1). In other words, taking $U_{i}:=V_{i+1}$ for
each $i\in[k-1]$ the family
$\mathcal{H}=\\{H_{1},\dots,H_{|Z|}\\}=\\{L_{v}(H):v\in Z\\}$ of link graphs
of vertices of $Z$ is a family of $(k-1)$-partite $(k-1)$-graphs with common
vertex classes $U_{1},\dots U_{k-1}$ each of size $n$ which satisfies
conditions (i) and (ii) above (with the same $q$ there as here and with
$m=|Z|-q$). So by Lemma 2.5 (described above) there exists a rainbow matching
in $\mathcal{H}$ of size $m+q=|Z|$.

Taking each edge of this matching together with the corresponding vertex of
$Z$ gives a matching $M_{rainbow}$ in $H$ of size $|Z|$ which covers every
vertex of $Z$. Using the fact that vertices in $X$ form edges with many
$(k-1)$-tuples in $M$, and that crossing $(k-1)$-tuples avoiding $V_{1}$ have
many neighbours in $V_{1}$, it is then straightforward to extend $M_{rainbow}$
to a perfect matching in $H$ (see the proof of Theorem 1.7 in Section 3 for
the details).

###  1.3. Notation

We write $[n]:=\\{1,2,\ldots,n\\}$ and $[a,b]:=\\{a,a+1,\ldots,b\\}$ for all
$b>a$ and $a,b,n\in\mathbb{N}$. If $H$ is a $k$-graph with $k\geq 3$, then for
a $(k-1)$-tuple of vertices $S\subseteq V(H)$, we write $N_{H}(S):=\\{v\in
V(H):S\cup\\{v\\}\in E(H)\\}$ for the _neighbourhood_ of $S$ in $H$, so
$\deg_{H}(S)=|N_{H}(S)|$. On the other hand, if $G$ is a graph then for a set
of vertices $S\subseteq V(G)$ we write $N_{G}(S):=\bigcup_{x\in S}N_{G}(x)$;
there should be no confusion as the former notation will never be used in the
graph case. In both cases we may omit the subscript when the host graph is
clear from the context.

Throughout the paper, in any condition of the form
$\delta_{[k]\setminus\\{i\\}}(H)\geq a_{i}$ it should be assumed that $a_{i}$
is a non-negative integer.

##  2\. Matchings under a combination of degree and multiplicity

In this section we prove the key lemma we need for the proof of Theorem 1.7,
namely Lemma 2.5. As described in Section 1.2, the setting for this is that we
have a family $\mathcal{H}=\\{H_{1},\dots,H_{t}\\}$ of $k$-partite $k$-graphs
on common vertex classes $V_{1},\dots,V_{k}$, and each $k$-graph $H_{j}$ in
$\mathcal{H}$ satisfies the multipartite codegree condition that
$\delta_{[k]\setminus\\{i\\}}(H_{j})\geq a_{i}$ for each $i\in[k]$. We write
$q:=\sum_{i=1}^{k}a_{i}$, and this is the key parameter concerning degrees in
each $H_{j}$. Our key lemma, Lemma 2.5, then says that if we also assume the
multiplicity condition that each crossing $k$-tuple is contained in at least
$m$ of the $k$-graphs in $\mathcal{H}$, and the necessary condition that
$t\geq m+q$, then (under some additional technical assumptions) there must be
a rainbow matching in $\mathcal{H}$ of size $m+q$. We begin working towards
this goal by proving the following weaker version of the lemma, in which we
assume that $t\geq m+q+k-1$, meaning that our matching may leave $k-1$ colours
unused; the lemma allows us some control over which colours these are. Note
that here we also allow the sizes of vertex classes to differ from one
another, to enable the lemma to be applied after a small number of vertices
have been deleted from our original vertex classes.

######  Lemma 2.1.

Let $H_{1},\dots,H_{t}$ be $k$-partite $k$-graphs with common vertex classes
$V_{1},\dots,V_{k}$ each of size at least $n$. Suppose that

  1. (i)

for each $i\in[k]$ and $j\in[t]$ we have
$\delta_{[k]\setminus\\{i\\}}(H_{j})\geq a_{i}$, and

  2. (ii)

each crossing $k$-tuple appears in at least $m$ of the $k$-graphs $H_{j}$.

Also write $q:=\sum_{i\in[k]}a_{i}$. If $n,t\geq m+q+k-1$ then for each set
$C\subseteq[t]$ with size $|C|\leq q/k$ there is a rainbow matching in
$\mathcal{H}:=\\{H_{j}:j\in[t]\\}$ of size $m+q$ which includes an edge of
colour $j$ for each $j\in C$.

###### Proof.

We first show that $\mathcal{H}$ admits a rainbow matching of size $m+q$. Let
$M$ be a largest rainbow matching in $\mathcal{H}$, and suppose for a
contradiction that $|M|\leq m+q-1$. Also let $D\subseteq[t]$ be the set of
colours not used by $M$, so $|D|=t-|M|\geq k$. Since $|V_{i}|\geq n\geq
m+q+k-1$ for each $i\in[k]$, we may choose $k$ pairwise-disjoint crossing
$(k-1)$-tuples $t_{1},\ldots,t_{k}$, each disjoint from $V(M)$, such that
$t_{i}$ avoids $V_{i}$ for each $i\in[k]$, as well as a crossing $k$-tuple $f$
which is disjoint from $V(M)$ and each of the $t_{i}$. Let $F:=\\{j\in[t]:f\in
E(H_{j})\\}$, so $F$ is the set of colours that $f$ could take in a rainbow
matching. We have $|F|\geq m$ by (ii), and also $F\cap D=\emptyset$ as
otherwise we could add $f$ in the corresponding colour to extend $M$ to a
larger rainbow matching. Let $M^{\prime}\subseteq M$ consist of all edges of
$M$ whose colour is not in $F$, so $|M^{\prime}|=|M|-|F|\leq q-1$.

For each $v\in V(M)$ let $e_{v}$ denote the edge of $M$ which contains $v$.
Now consider any $i\in[k]$, $j\in D$ and vertex $v\in N_{H_{j}}(t_{i})$. We
must have $v\in V(M)$, as otherwise we could extend $M$ to a larger rainbow
matching by adding the edge $t_{i}\cup\\{v\\}$ in colour $j$ to obtain a
contradiction. This means $e_{v}$ is defined; moreover if $e_{v}$ has colour
$c$ for some $c\in F$, then $(M\setminus\\{e_{v}\\})\cup\\{f,\\{v\\}\cup
t_{i}\\}$ is a larger rainbow matching in $\mathcal{H}$ (where $f$ has colour
$c$ and $\\{v\\}\cup t_{i}$ has colour $j$), again giving a contradiction. We
conclude that for every $i\in[k]$ and $j\in D$ we have $e_{v}\in M^{\prime}$
for every vertex $v\in N_{H_{j}}(t_{i})$.

Since $|D|\geq k$, we may choose distinct $d_{1},\ldots,d_{k}\in D$ and note
for each $i\in[k]$ that $N_{H_{d_{i}}}(t_{i})$ has at least $a_{i}$ neighbours
in $V_{i}$, each in an edge in $M^{\prime}$. Since $|M^{\prime}|\leq q-1$, by
(i) and our previous observation, there exist $i,i^{\prime}\in[k]$ with $i\neq
i^{\prime}$ and $e\in M^{\prime}$ such that $N_{H_{d_{i}}}(t_{i})\cap
e\neq\emptyset$ and $N_{H_{d_{i^{\prime}}}}(t_{i^{\prime}})\cap
e\neq\emptyset$. So there are vertices $v\in V_{i}$ and $v^{\prime}\in
V_{i^{\prime}}$ with $v\in e\cap N_{H_{d_{i}}}(t_{i})$ and $v^{\prime}\in
e\cap N_{H_{d_{i^{\prime}}}}(t_{i^{\prime}})$ respectively. It follows that
$(M\setminus\\{e\\})\cup\\{t_{i}\cup\\{v\\},t_{i^{\prime}}\cup\\{v^{\prime}\\}\\}$,
where $t_{i}\cup\\{v\\}$ and $t_{i^{\prime}}\cup\\{v^{\prime}\\}$ have colour
$d_{i}$ and $d_{i^{\prime}}$ respectively, is a larger rainbow matching in
$\mathcal{H}$, a contradiction.

We conclude that $\mathcal{H}$ admits a rainbow matching $M$ of size $m+q$.
Suppose that there is some $j\in C$ for which $M$ does not include an edge of
colour $j$. Fix $i$ for which $a_{i}$ is largest, so $a_{i}\geq q/k$, and let
$f$ be a crossing $(k-1)$-tuple which avoids $V_{i}$ and does not intersect
$V(M)$ (this is possible since $n\geq m+q+1$). Since fewer than $|C|\leq q/k$
vertices of $V_{i}$ lie in edges of $M$ with colours in $C$, but
$|N_{H_{j}}(f)|\geq a_{i}\geq q/k$, we may choose $v\in V_{i}$ for which
$e:=f\cup\\{v\\}\in E(H_{j})$ and either $v\notin V(M)$ or $v$ is contained in
an edge $e^{\prime}\in M$ whose colour is not in $C$. In the former case
choose any edge $e^{\prime}\in M$ whose colour is not in $C$. In both cases
$(M\setminus e^{\prime})\cup\\{e\\}$, with $e$ having colour $j$, is then a
rainbow matching of size $m+q$ which, compared to $M$, includes one more edge
whose colour is in $C$. Iterating this process gives the result. ∎

Our next lemma is a type of stability result: it states that if $t$ is not too
much larger than $q$ then the multipartite degree assumption of Lemma 2.1 on
its own is sufficient to guarantee a perfect rainbow matching in $\mathcal{H}$
unless the family of $k$-graphs $\mathcal{H}$ is extremal in the sense that
almost all of the $k$-graphs in $\mathcal{H}$ admit dominating sets of size
close to $q$ (note that the degree condition immediately implies that every
dominating set must have size at least $q$).

######  Lemma 2.2.

Let $V_{1},V_{2},\dots,V_{k}$ be disjoint sets of vertices, each of size $n$,
and let $V:=\bigcup_{i\in[k]}V_{i}$. Let $H_{1},\dots,H_{t}$ be $k$-partite
$k$-graphs each with vertex classes $V_{1},\dots,V_{k}$, and suppose that for
each $i\in[k]$ and $j\in[t]$ we have $\delta_{[k]\setminus\\{i\\}}(H_{j})\geq
a_{i}$. Write $q:=\sum_{i\in[k]}a_{i}$.

For every $\varepsilon\in(0,1)$, if $t\leq(1+\varepsilon)q$ and $n\geq
8k^{3}q/\varepsilon$ then either

  1. (i)

$\mathcal{H}:=\\{H_{1},\dots,H_{t}\\}$ admits a perfect rainbow matching, or

  2. (ii)

there is a set $C\subseteq[t]$ of size at least $(1-\varepsilon)q$ such that
for each $j\in C$ the graph $H_{j}$ admits a dominating set of size at most
$(1+2k\varepsilon)q$.

###### Proof.

Suppose that property (ii) does not hold. By relabelling the $H_{i}$, we may
assume that the first $\ell:=t-q+\lceil\varepsilon q\rceil$ graphs
$H_{1},H_{2},\dots,H_{\ell}$ each do not admit a dominating set of size at
most $(1+2k\varepsilon)q$. We begin by proceeding through the graphs $H_{j}$
in reverse order, setting aside for each either a vertex $v_{j}$ or an edge
$e_{j}$, which we will subsequently use to construct a perfect rainbow
matching in $\mathcal{H}$. We also keep track of the sets $U_{j}$ of all
vertices in $V$ which have not appeared as $v_{j^{\prime}}$ or in
$e_{j^{\prime}}$ for any previously-considered $j^{\prime}>j$ (note that
$U_{j}$, like $V$, may contain vertices from all vertex classes). So we set
$U_{t}:=V$, and then for each $j=t,t-1,\dots,1$ (in that order) we do the
following.

  1. (a)

If $H_{j}[U_{j}]$ admits a matching of size $kj$, then set $U_{j-1}=U_{j}$.

  2. (b)

Otherwise, if $H_{j}[U_{j}]$ contains a vertex $x_{j}$ with
$\deg_{H_{j}[U_{j}]}(x_{j})\geq kjn^{k-2}$, then set
$U_{j-1}=U_{j}\setminus\\{x_{j}\\}$.

  3. (c)

Otherwise, arbitrarily choose an edge $e_{j}\in H_{j}[U_{j}]$ and set
$U_{j-1}=U_{j}\setminus e_{j}$.

The key claim is that we can do this for every $j$; in other words, one of
(a), (b) and (c) will always be possible. To show this we first argue by
induction on $t$ that for each $j\geq\ell$ either (a) or (b) will be possible,
meaning that for each such $j$ we have $|V\setminus U_{j}|\leq t-j$. If
$H_{j}[U_{j}]$ admits a matching of size $kj$ then (a) is possible, so we may
assume that a largest matching in $H_{j}[U_{j}]$ has size less than $kj$,
whereupon the vertex set of this matching is a dominating set $D$ in
$H_{j}[U_{j}]$ of size at most $k^{2}j$. For each $i\in[k]$ choose a set of
exactly $\lceil n^{k-1}/2\rceil$ crossing $(k-1)$-tuples $f$ which avoid
$V_{i}$ and have $f\subseteq U_{j}\setminus D$; this is possible since there
are $n^{k-1}$ crossing $(k-1)$-tuples avoiding $V_{i}$ and $|(V\setminus
U_{j})\cup D|\leq t+k^{2}t\leq n/3$. Each such $f$ has at least $a_{i}$
neighbours in $V_{i}$, each of which must lie in $D$ since $D$ is a dominating
set. Summing over each $i$ we obtain $q\lceil n^{k-1}/2\rceil$ edges of
$H_{j}$ which contain a vertex of $D$. Since $|V\setminus U_{j}|\leq t-j$ at
most $(t-j)\lceil n^{k-1}/2\rceil$ of these edges are not in $H_{j}[U_{j}]$.
So for $j\geq\ell=t-q+\lceil\varepsilon q\rceil$ we find that there are at
least $(q-t+j)\lceil n^{k-1}/2\rceil\geq\varepsilon qn^{k-1}/2$ edges of
$H_{j}[U_{j}]$ which contain a vertex of $D$. Since $|D|\leq k^{2}j$, by an
averaging argument we find that some vertex $x_{j}\in D$ has

$\deg_{H_{j}[U_{j}]}(x_{j})\geq\frac{\varepsilon qn^{k-1}}{2k^{2}j}\geq
kjn^{k-2},$

where the final inequality holds since $j^{2}\leq
t^{2}\leq(1+\varepsilon)^{2}q^{2}\leq 4q^{2}$ and $n\geq 8k^{3}q/\varepsilon$.
We conclude that, as claimed, (b) is possible.

It remains to consider the cases when $j\leq\ell-1\leq t-q+\varepsilon q\leq
2\varepsilon q$. For this, first note that since either (a) or (b) was chosen
for each $j\geq\ell$, in each such case we have

$|V\setminus
U_{j}|\leq(t-\ell+1)+k\cdot(\ell-1)=t+(k-1)(\ell-1)\leq(1+\varepsilon)q+2(k-1)\varepsilon
q\leq(1+2k\varepsilon)q.$

The fact that $H_{j}$ has no dominating set of size at most
$(1+2k\varepsilon)q$ then implies that $V\setminus U_{j}$ is not a dominating
set in $H_{j}$, and therefore we may choose an edge $e_{j}\in H_{j}[U_{j}]$ as
claimed.

To complete the proof we now use the chosen vertices and edges to build a
rainbow matching $M_{t}$ in $\mathcal{H}$, giving property (i). Initially set
$M_{0}=\emptyset$; by adding edges one by one we will build a rainbow matching
$M_{j}$ of size $j$ in $\\{H_{1}[U_{j}],\dots,H_{j}[U_{j}]\\}$ for each
$j\in[t]$ (note in particular that for each $j\in[t]$ the matching $M_{j}$
will only use vertices in $U_{j}$).

For $j=1,2,\dots,t$:

  1. (1)

If we chose an edge $e_{j}$ in $H_{j}[U_{j}]$, then $e_{j}$ is already
defined; observe that by definition of $U_{j-1}$ we know that $e_{j}$ is
disjoint from $V(M_{j-1})$.

  2. (2)

If we chose a vertex $x_{j}$, then choose an edge $e_{j}$ in $H_{j}[U_{j}]$
which is disjoint from $V(M_{j-1})$. This is possible since $x_{j}\notin
V(M_{j-1})$ by definition of $U_{j-1}$, and furthermore we have
$\deg_{H_{j}[U_{j}]}(x_{j})\geq kjn^{k-2}>|V(M_{j-1})|n^{k-2}$, and the latter
term is an upper bound on the number of edges containing $x_{j}$ which meet
$V(M_{j-1})$.

  3. (3)

Otherwise $H_{j}[U_{j}]$ admits a matching of size $kj$; since
$|V(M_{j-1})|=k(j-1)<kj$ we may choose an edge $e_{j}$ in $H_{j}[U_{j}]$ which
is disjoint from $V(M_{j-1})$.

  4. (4)

In each case we add $e_{j}$ to $M_{j-1}$ to obtain the desired rainbow
matching $M_{j}$ of size $j$ in $\\{H_{1}[U_{j}],\dots,H_{j}[U_{j}]\\}$.

At the conclusion of this process, $M_{t}$ is a rainbow matching of size $t$
in $\\{H_{1},\dots,H_{t}\\}$. ∎

The next proposition helps us to use the dominating sets obtained by applying
Lemma 2.2 in the case where $\mathcal{H}$ does not contain a perfect rainbow
matching, by showing that almost all vertices in these dominating sets must
have very high degrees in their host graphs.

######  Proposition 2.3.

Let $H$ be a $k$-partite $k$-graph with vertex classes $V_{1},\dots,V_{k}$
each of size $n$, such that for each $i\in[k]$ we have
$\delta_{[k]\setminus\\{i\\}}(H)\geq a_{i}$. Write $q:=\sum_{i\in[k]}a_{i}$
and fix a real number $\mu\geq 0$. If $n\geq 5(1+\mu)q$ and $H$ admits a
dominating set $D$ of size at most $(1+\mu)q$, then at least $(1-2\mu)q$
vertices $x\in D$ have $\deg_{H}(x)\geq n^{k-1}/2$.

###### Proof.

For $q=0$ the statement is vacuous, so we may assume that $q\geq 1$ and so
$n\geq 5$. Let $3/4\leq\beta\leq 4/5$ be such that $\beta n^{k-1}$ is an
integer. For each $i\in[k]$ let $F_{i}$ be a set of $\beta n^{k-1}$ crossing
$(k-1)$-tuples, each of which does not intersect $D\cup V_{i}$. This is
possible since there are $n^{k-1}$ crossing $(k-1)$-tuples which avoid
$V_{i}$, and at most $|D|n^{k-2}\leq n^{k-1}/5$ of these intersect $D$. Write
$F=\bigcup_{i\in[k]}F_{i}$; we now double-count the set $X:=\\{(x,f):x\in
D,f\in F,\\{x\\}\cup f\in E(H)\\}$. First note that for each $i\in[k]$, each
$f\in F_{i}$ has at least $a_{i}$ neighbours in $V_{i}$, all of which must lie
in $D$ since $D$ is a dominating set which does not intersect $f$. So

$|X|\geq\sum_{i\in[k]}a_{i}|F_{i}|=\sum_{i\in[k]}a_{i}\cdot\beta n^{k-1}=\beta
qn^{k-1}.$

Now let $A\subseteq D$ consist of all vertices $x\in D$ which lie in at least
$n^{k-1}/2$ pairs in $X$. Since every vertex of $D$ can be in at most $\beta
n^{k-1}$ pairs in $X$, we then have

$|X|<\left(|D|-|A|\right)\cdot\frac{n^{k-1}}{2}+|A|\cdot\beta
n^{k-1}=\frac{|D|n^{k-1}}{2}+(\beta-1/2)|A|n^{k-1}\leq\frac{(1+\mu)qn^{k-1}}{2}+(\beta-1/2)|A|n^{k-1}.$

Combining the two displayed inequalities and noting that $1/(2\beta-1)\leq 2$,
we obtain $|A|\geq(1-2\mu)q$, and the conclusion follows. ∎

The final proposition we need concerns perfect matchings in bipartite graphs.
Let $G$ be a bipartite graph with vertex classes $A$ and $B$, where every
vertex in $A$ has degree close to $|A|$ (we don’t control the size of $B$ at
all beyond this, or place any degree condition on vertices in $B$). The idea
expressed in this proposition is that either the neighbourhoods of vertices in
$A$ do not mostly overlap extensively, in which case there should be a
matching in $G$ of size $|A|$ even after the deletion of any small set of
vertices of $B$, or they do mostly overlap extensively, in which case we can
remove a few vertices of $A$ to obtain a subset $X\subseteq A$ for which some
usefully-sized subset $B^{\prime}\subseteq B$ is ‘highly-matchable’ to $X$,
meaning that every subset $A^{\prime}\subseteq X$ of size $|B^{\prime}|$ can
be perfectly matched to $B^{\prime}$.

######  Proposition 2.4.

Fix a positive integer $q$ and a real number $\mu$ with $0\leq\mu\leq 1/50$.
Let $G$ be a bipartite graph with vertex classes $A$ and $B$, where
$|A|\leq(1+\mu)q$, and suppose that $\deg(x)\geq(1-\mu)q$ for every $x\in A$.
We then must have either

  1. (i)

for every set $Y\subseteq B$ with $|Y|\leq\mu q$ there exists a matching of
size $|A|$ in $G[A\cup(B\setminus Y)]$, or

  2. (ii)

there exist subsets $X\subseteq A$ and $B^{\prime}\subseteq B$ with
$|X|\geq(1-2\mu)q$ and $|B^{\prime}|=\lfloor q/2\rfloor$ such that for every
subset $A^{\prime}\subseteq X$ of size $\lfloor q/2\rfloor$ there is a perfect
matching in $G[A^{\prime}\cup B^{\prime}]$.

###### Proof.

We may assume that there exists $Y\subseteq B$ with $|Y|\leq\mu q$ for which
there does not exist a matching of size $|A|$ in $G[A\cup(B\setminus Y)]$, as
otherwise we obtain (i). By Hall’s Marriage Theorem it follows that some non-
empty $X\subseteq A$ has $|N_{X}\setminus Y|<|X|$, where we write
$N_{X}:=N_{G}(X)$. So $(1-\mu)q\leq|N_{X}|<|X|+|Y|\leq|A|+|Y|\leq(1+2\mu)q$,
where the first inequality holds since each vertex $x\in A$ has
$\deg(x)\geq(1-\mu)q$. This in turn implies that
$(1-2\mu)q\leq(1-\mu)q-|Y|<|X|\leq|A|\leq(1+\mu)q$.

Observe that for each $x\in X$ there are at most $3\mu q$ vertices $y\in
N_{X}$ for which $xy$ is not an edge. So the number of pairs $xy$ with $x\in
X$ and $y\in N_{X}$ for which $xy$ is not an edge is at most $3\mu q|X|\leq
4\mu q^{2}$. It follows that at most $20\mu q$ vertices of $N_{X}$ lie in more
than $q/5$ such pairs. So we may choose a set $B^{\prime}\subseteq
N_{X}\subseteq B$ of size $|B^{\prime}|=\lfloor q/2\rfloor$ not including any
such vertex, meaning that every $y\in B^{\prime}$ has at least $|X|-q/5$
neighbours in $X$.

Now consider any set $A^{\prime}\subseteq X$ of size $\lfloor q/2\rfloor$. Our
choice of $B^{\prime}$ ensures that each vertex of $B^{\prime}$ has at least
$|A^{\prime}|-q/5\geq|A^{\prime}|/2$ neighbours in $A^{\prime}$, whilst each
vertex $x\in A^{\prime}$ has at least $|B^{\prime}|-3\mu q\geq|B^{\prime}|/2$
neighbours in $B^{\prime}$ (the calculations of this sentence actually only
hold for $q\geq 4$, but the proposition is elementary to check for smaller
$q$). It follows that $G[A^{\prime}\cup B^{\prime}]$ admits a perfect
matching, so we have (ii). ∎

Finally we arrive at the main result of this section, which is the key step in
the proof of Theorem 1.7.

######  Lemma 2.5.

Let $V_{1},V_{2},\dots,V_{k}$ be disjoint sets of vertices each of size $n$,
and let $V=\bigcup_{i\in[k]}V_{i}$. Let $H_{1},\dots,H_{t}$ be $k$-partite
$k$-graphs each with vertex classes $V_{1},\dots,V_{k}$, and suppose that

  1. (i)

for each $i\in[k]$ and $j\in[t]$ we have
$\delta_{[k]\setminus\\{i\\}}(H_{j})\geq a_{i}$, and

  2. (ii)

each crossing $k$-tuple appears in at least $m$ of the $k$-graphs $H_{j}$.

Also write $q:=\sum_{i\in[k]}a_{i}$. If $n\geq\max(1600k^{4}q,100k^{6})$ and
$m+q\leq t\leq(1+1/200k)q$, then $\mathcal{H}:=\\{H_{1},\dots,H_{t}\\}$ admits
a rainbow matching of size $m+q$.

###### Proof.

Suppose first that $\lfloor{q/2}\rfloor\geq k-1$ (we address the other,
simpler, case later). Set $\eta:=1/200k$, so $t\leq(1+\eta)q$ and $n\geq
8k^{3}q/\eta$. These bounds permit us to apply Lemma 2.2, by which we may
assume that there exists a set $A\subseteq[t]$ of size at least $(1-\eta)q$
such that for each $j\in A$ the graph $H_{j}$ admits a dominating set of size
at most $(1+2k\eta)q$, and by Proposition 2.3 it follows that for each $j\in
A$ there exists a set $X_{j}\subseteq V$ of size $|X_{j}|\geq(1-4k\eta)q$ such
that each vertex $x\in X_{j}$ has $\deg_{H_{j}}(x)\geq n^{k-1}/2$. Form an
auxiliary bipartite graph $G$ whose vertex classes are $A$ and $V$ in which
$jx$ is an edge if $\deg_{H_{j}}(x)\geq n^{k-1}/2$. So our prior observation
implies that $\deg_{G}(j)\geq(1-4k\eta)q$ for each $j\in A$. By Proposition
2.4, taking $\mu:=4k\eta=1/50$ and s:= $\lfloor q/2\rfloor$, we find that
either

  1. (1)

for every set $Y\subseteq V$ with $|Y|\leq\mu q$ there exists a matching of
size $|A|$ in $G[A\cup(V\setminus Y)]$, or

  2. (2)

there exist subsets $X\subseteq A$ and $Z\subseteq V$ with $|X|\geq(1-2\mu)q$
and $|Z|=s$ such that for any $A^{\prime}\subseteq X$ of size $s$ there is a
perfect matching in $G[A^{\prime}\cup Z]$.

If (1) holds, then arbitrarily choose a perfect rainbow matching $M$ in the
family $\\{H_{j}:j\in[t]\setminus A\\}$. This is possible since $|[t]\setminus
A|\leq 2\eta q\leq q/k\leq\max_{i\in[k]}a_{i}$, so we may form $M$ by choosing
$t-|A|$ pairwise-disjoint crossing $(k-1)$-tuples which avoid
$V_{i^{\prime}}$, where $i^{\prime}:=\max_{i\in[k]}a_{i}$, and greedily
extending each to an edge of the respective $H_{j}$ so that no vertex is used
more than once. Let $Y:=V(M)$, so $|Y|=k|M|\leq 2k\eta q\leq\mu q$. It follows
by (1) that $G[A\cup(V\setminus Y)]$ admits a matching $M_{G}$ which covers
the vertices of $A$, which we will shortly use to greedily extend $M$ to a
perfect rainbow matching in $\mathcal{H}$.

If instead (2) holds, then set $V_{i}^{\prime}:=V_{i}\setminus Z$ for each
$i\in[k]$, $V^{\prime}:=V\setminus Z$, $n^{\prime}:=n-s$, $q^{\prime}=q-s$ and
$H^{\prime}_{j}:=H_{j}[V^{\prime}]$ for each $j\in[t]$. Then
$H^{\prime}_{1},\dots,H^{\prime}_{t}$ are $k$-partite $k$-graphs with common
vertex classes $V^{\prime}_{1},\dots,V^{\prime}_{k}$ each of size at least
$n^{\prime}$ such that each crossing $k$-tuple appears in at least $m$ of the
graphs $H^{\prime}_{1},\dots,H^{\prime}_{t}$. Moreover, for each $i\in[k]$ and
$j\in[t]$ we have $\delta_{[k]\setminus\\{i\\}}(H_{j})\geq
a^{\prime}_{i}:=a_{i}-|Z\cap V_{i}|$, and
$\sum_{i\in[k]}a^{\prime}_{i}=\sum_{i\in[k]}a_{i}-|Z|=q^{\prime}$. Since
$t\geq m+q=m+q^{\prime}+s\geq m+q^{\prime}+k-1$, we may apply Lemma 2.1 with
$[t]\setminus X$ in place of $C$ to obtain a rainbow matching $M$ of size
$m+q^{\prime}=m+q-s$ in the family $\\{H^{\prime}_{1},\dots,H^{\prime}_{t}\\}$
such that $M$ includes an edge of colour $j$ for every $j\in[t]\setminus X$
(i.e. $M$ includes distinct edges for each such $j$). Let $U\subseteq[t]$ be
the set of all $j\in[t]$ for which $M$ has no edge of colour $j$, so
$U\subseteq X$ and furthermore $|U|=t-(m+q-s)\geq s$. So we may arbitrarily
choose a subset $A^{\prime}\subseteq U\subseteq X$ of size $s$, whereupon (2)
implies that there is a perfect matching $M_{G}$ in $G[A^{\prime}\cup Z]$,
which we will use to extend $M$ to a rainbow matching in $G$ of size $m+q$.

In both cases we now use the matching $M_{G}$ to greedily extend $M$ to a
rainbow matching of size $|M|+|M_{G}|$ in $\mathcal{H}$. Observe that each
edge $e\in M_{G}$ has the form $j_{e}x_{e}$ for some $j_{e}\in A$ and
$x_{e}\in V$. For each edge $e\in M_{G}$ in turn we choose an edge $f_{e}$ of
$H_{j_{e}}$ with $x_{e}\in f_{e}$ such that $f_{e}$ does not intersect $V(M)$
or any previously-chosen edge $f_{e^{\prime}}$ and also $f_{e}$ does not
contain any vertex $x_{e^{\prime}}$ for $e^{\prime}\neq e$. Observe for this
that since $e$ is an edge of $G$ there are at least
$\deg_{H_{j_{e}}}(x_{e})\geq n^{k-1}/2$ edges of $H_{j_{e}}$ containing
$x_{e}$, and the number of these edges which we are forbidden from using is at
most $(|V(M)|+k|M_{G}|)n^{k-2}\leq ktn^{k-2}$, so it is always possible to
choose an edge $f_{e}$ with the required properties. The chosen edges $f_{e}$
then form a perfect rainbow matching $M^{\prime}$ of size $|M_{G}|$ in the
family $\\{H_{j_{e}}:e\in M_{G}\\}$, and so $M^{*}:=M\cup M^{\prime}$ is a
rainbow matching in $\mathcal{H}$ of size $|M|+|M_{G}|$. It follows that
$M^{*}$ is perfect if (1) holds, and has size $m+q$ if (2) holds; either way
this completes the proof.

It remains to consider the case when $\lfloor{q/2}\rfloor<k-1$, in which case
we have $q<2k$, so our assumption that $m+q\leq t\leq(1+1/200k)q$ implies that
$m=0$ and $t=q$; in particular, our goal in this case is to show that
$\mathcal{H}$ admits a perfect rainbow matching. Set $\varepsilon=1/3kq$ and
observe that we have $n\geq 100k^{6}\geq 25k^{4}q^{2}\geq
8k^{3}q/\varepsilon$, so again we may apply Lemma 2.2, by which we may assume
that there exists a set $A\subseteq[t]$ of size $q=t$ such that for each $j\in
A$ the graph $H_{j}$ admits a dominating set of size at most $q$. In other
words, for every $j\in[t]$ there exists a dominating set $S_{j}$ in $H_{j}$ of
size at most $q$. Write $X:=\bigcup_{j\in[t]}S_{j}$, so $|X|\leq qt=q^{2}$,
and define $X_{i}:=X\cap V_{i}$ for each $i\in[k]$. We now build our desired
matching greedily; for this we set $M_{0}:=\emptyset$, and for each $j\in[t]$
in turn will add an edge to $M_{j-1}$ to form a perfect rainbow matching
$M_{j}$ in $\\{H_{1},\dots,H_{j}\\}$, whilst maintaining the property that
every edge in $M_{j}$ has at most one vertex in $X$. So fix some $j\in[t]$,
and note that since each edge in $M_{j-1}$ has at most one vertex in $X$, we
have $\sum_{i\in[k]}a_{i}=q=t>j-1=|V(M_{j-1})\cap
X|=\sum_{i\in[k]}|V(M_{j-1})\cap X_{i}|$, and so there exists some $i\in[k]$
with $|V(M_{j-1})\cap X_{i}|<a_{i}$. Choose a crossing $(k-1)$-tuple $f_{j}$
of vertices in $V\setminus(V(M_{j-1})\cup X)$ which avoids $V_{i}$ (this is
possible since $n>kq+q^{2}\geq|V(M_{j-1})\cup X|$), and observe that $f$ has
at least $a_{i}$ neighbours in $V_{i}$, all of which must lie in
$S_{j}\subseteq X$, so there is at least one vertex $u_{j}\in X_{i}\setminus
V(M_{j-1})$ for which $e_{j}=f_{j}\cup\\{u_{j}\\}$ is an edge of $H_{j}$. Set
$M_{j}:=M_{j-1}\cup\\{e_{j}\\}$, and observe that $M_{j}$ is a perfect rainbow
matching in $\\{H_{1},\dots,H_{j}\\}$ in which every edge has at most one
vertex in $X$. Having done this for every $j\in[t]$, the final matching
$M_{t}$ is the desired perfect rainbow matching in $\mathcal{H}$. ∎

##  3\. Proof of Theorem 1.7

We begin our proof of Theorem 1.7 with two propositions regarding the link
graphs of vertices in the first vertex class $V_{1}$. The first states that
for large sets $U\subseteq V_{1}$, every crossing $(k-1)$-tuple avoiding
$V_{1}$ must appear in many of the link graphs $\\{L_{v}(H)\\}_{v\in U}$.

######  Proposition 3.1.

Let $H$ be a $k$-partite $k$-graph whose vertex classes $V_{1},\dots,V_{k}$
each have size $n$, with the property that
$\delta_{[k]\setminus\\{1\\}}(H)\geq a_{1}$. For every set $U\subseteq V_{1}$
and each crossing $(k-1)$-tuple $f$ avoiding $V_{1}$, there are at least
$|U|-(n-a_{1})$ vertices $v\in U$ for which $f\in L_{v}(H)$.

###### Proof.

Observe that $f$ has at least $a_{1}$ neighbours in $V_{1}$, of which at most
$n-|U|$ are outside $U$, meaning that $f$ has at least $a_{1}-(n-|U|)$
neighbours $v\in U$, and $f$ appears in $L_{v}(H)$ for each such $v$. ∎

Our second proposition asserts that for any matching $M$ in the complete
$(k-1)$-partite $(k-1)$-graph on $V_{2},\ldots,V_{k}$, there is a large subset
$U\subseteq V_{1}$ such that $L_{v}(H)$ contains many edges of $M$ for every
$v\in U$. In fact we give two forms of this statement, varying in how we
interpret ‘large’ and ‘many’. The first version is a looser result which holds
for a wider range of values of $q$, which will be sufficient for the proof of
Theorem 1.7 in the case where $q\geq 400k^{2}$. For smaller values of $q$ we
instead use the second version of the statement, which gives a more precise
result but which is only valid for $q\leq\sqrt{\frac{n}{k+1}}$ (we will in
fact only use it in the case where $q<400k^{2}$).

######  Proposition 3.2.

For each $k\geq 3$ and every $\varepsilon\in(0,1)$ there exists
$n_{0}\in\mathbb{N}$ such that the following statements hold. Let $H$ be a
$k$-partite $k$-graph with vertex classes $V_{1},\ldots,V_{k}$ each of size
$n\geq n_{0}$ in which $\delta_{[k]\setminus\\{i\\}}(H)\geq a_{i}$ for each
$i\in[k]$. Suppose also that $a_{1}\geq a_{2}\geq\ldots\geq a_{k}$ and
$\sum_{i\in[k]}a_{i}>n-k$, and write $q:=\sum_{i\in[2,k]}a_{i}$. Let $M$ be a
perfect matching in the complete $(k-1)$-partite $(k-1)$-graph on vertex sets
$V_{2},\ldots,V_{k}$.

  1. (i)

If $2k/\varepsilon\leq q\leq\frac{\varepsilon n}{8k}$, then there exists a
subset $U\subseteq V_{1}$ with $|U|\geq n-(1+\varepsilon)q$ such that every
$u\in U$ has $|L_{u}(H)\cap M|\geq(1+\varepsilon)kq$.

  2. (ii)

If $q\leq\sqrt{\frac{n}{k+1}}$, then there exists a subset $U\subseteq V_{1}$
with $|U|\geq a_{1}$ such that every $u\in U$ has $|L_{u}(H)\cap M|\geq
n-a_{1}+(k-1)q$.

###### Proof.

Let $P$ be the set of pairs $(u,f)$ with $u\in V_{1}$ and $f\in M$ such that
$\\{u\\}\cup f\in E(H)$. Since $|M|=n$ and each $f\in M$ has at least $a_{1}$
neighbours in $V_{1}$ we have $|P|\geq a_{1}n$. So, if we suppose for a
contradiction that (i) fails, then we have

$(n-k-q)n<a_{1}n\leq|P|<(n-(1+\varepsilon)q)\cdot
n+(1+\varepsilon)q\cdot(1+\varepsilon)kq<(n-q)n-\varepsilon qn+4kq^{2},$

where the first inequality holds since $a_{1}+q=\sum_{i\in[k]}a_{i}>n-k$, by
assumption. It follows that $kn+4kq^{2}>\varepsilon qn$, from which a
contradiction arises because our bounds on $q$ give $kn\leq\varepsilon qn/2$
and $4kq^{2}\leq\varepsilon qn/2$. We conclude that (i) holds.

Similarly, if we suppose for a contradiction that (ii) fails, then we have

$a_{1}n\leq|P|\leq(a_{1}-1)\cdot
n+(n-a_{1}+1)\cdot(n-a_{1}+(k-1)q)<a_{1}n-n+(q+k)(kq+k),$

where the final inequality holds since $n-a_{1}<k+q$ (and each of these
variables are integers). It follows that $k(q+k)(q+1)>n$, but this contradicts
our assumption that $q\leq\sqrt{\frac{n}{k+1}}$ (for $n$ sufficiently large
with respect to $k$). We conclude that (ii) holds also. ∎

We can now give the proof of Theorem 1.7, which combines Propositions 3.1 and
3.2 with Lemma 2.5 before finishing with an application of Hall’s Theorem to
an appropriate auxiliary bipartite graph to obtain a matching in $H$ of the
desired size.

###### Proof of Theorem 1.7.

By reducing $a_{1}$ if necessary, we may assume that $\sum_{i\in[k]}a_{i}\leq
n$, so our goal is to show that $H$ contains a matching of size
$\sum_{i\in[k]}a_{i}$. If $\sum_{i\in[k]}a_{i}\leq n-k+2$ then we obtain a
matching of this size by Fact 1.5, so we may assume that
$\sum_{i\in[k]}a_{i}\geq n-k+3$ also. Define $q:=\sum_{i\in[2,k]}a_{i}$, so
$n-k+3-a_{1}\leq q\leq n-a_{1}$, and by assumption we have $q\leq
n/1600k^{4}$. Also let $K^{k-1}$ denote the complete $(k-1)$-partite
$(k-1)$-graph on vertex sets $V_{2},\ldots,V_{k}$, and arbitrarily choose a
matching $M$ of size $n$ in $K^{k-1}$.

Suppose first that $q\geq 400k^{2}$. Applying Proposition 3.2 with
$\varepsilon=1/200k$ we obtain a subset $X\subseteq V_{1}$ such that

  1. (i)

$n-(1+\varepsilon)q\leq|X|$, and

  2. (ii)

$|M\cap L_{u}(H)|\geq(1+\varepsilon)kq$ for every $u\in X$.

Since $a_{1}\geq n-q-k+3\geq n-(1+\varepsilon)q+1$ we may additionally insist
that $|X|\leq a_{1}$ (by removing vertices if necessary). Let
$Y:=V_{1}\setminus X$, so $n-a_{1}\leq|Y|\leq(1+\varepsilon)q$ by (i).
Applying Proposition 3.1 to $Y$ we find that each crossing $(k-1)$-tuple
avoiding $V_{1}$ appears in at least $m:=|Y|-(n-a_{1})\geq 0$ of the link
graphs $\\{L_{u}(H)\\}_{u\in Y}$. Since $q\leq n-a_{1}$ we have $|Y|\geq m+q$,
so by Lemma 2.5, applied with $m$ and $q$ as here and with $t=|Y|$, the family
$\\{L_{u}(H)\\}_{u\in Y}$ admits a rainbow matching $M_{rainbow}$ of size
$m+q\leq|Y|$. This means there is a set $Z\subseteq Y$ of size $m+q$ and a
bijection $\psi:Z\to M_{rainbow}$ such that for each $z\in Z$ we have
$\\{z\\}\cup\psi(z)\in E(H)$.

Let $M^{\prime}\subseteq M$ be the matching in $K^{k-1}$ consisting of all
edges of $M$ which do not intersect any edge of $M_{rainbow}$, and let $M^{*}$
be a matching in $K^{k-1}$ of size $n$ with $M^{\prime}\cup
M_{rainbow}\subseteq M^{*}$. Since $|M\setminus
M^{\prime}|\leq|V(M_{rainbow})|\leq(k-1)|Y|\leq(k-1)(1+\varepsilon)q$, by (ii)
we have for each $u\in X$ that

$\displaystyle|M^{*}\cap L_{u}(H)|$ $\displaystyle\geq|M^{\prime}\cap
L_{u}(H)|\geq|M\cap L_{u}(H)|-|M\setminus
M^{\prime}|\geq(1+\varepsilon)kq-(k-1)(1+\varepsilon)q\geq(1+\varepsilon)q.$

Set $U^{*}:=X\cup Z\subseteq V_{1}$, and form an auxiliary bipartite graph $B$
with vertex classes $U^{*}$ and $M^{*}$ in which, for each $u\in U^{*}$ and
$f\in M^{*}$, we have $uf\in E(B)$ if and only if $\\{u\\}\cup f\in E(H)$.

Consider a set $S\subseteq U^{*}$. If $|S|\geq n-a_{1}+1$, then by Proposition
3.1 each $f\in K^{k-1}$ has $|N_{H}(f)\cap S|\geq 1$, so $N_{B}(S)=M^{*}$ and
so $|N_{B}(S)|=n\geq|S|$. Alternatively, if $|S|\leq n-a_{1}$ and $S$ contains
a vertex $u\in X$, then $|N_{B}(S)|\geq|N_{B}(u)|=|M^{*}\cap
L_{u}(H)|\geq(1+\varepsilon)q\geq n-a_{1}\geq|S|$. Finally, if $S\subseteq Z$
then $z\psi(z)\in E(B)$ for each $z\in S$, so again we have
$|N_{B}(S)|\geq|S|$. We conclude that the bipartite graph $B$ satisfies Hall’s
criterion that $|N_{B}(S)|\geq|S|$ for every $S\subseteq U^{*}$, and therefore
contains a matching $M_{B}$ of size $|U^{*}|$. The edges $\\{u\\}\cup f$ for
each $uf\in M_{B}$ then form a matching in $H$ of size

$|U^{*}|=|X|+|Z|=n-|Y|+m+q=a_{1}+q=\sum_{i\in[k]}a_{i},$

as required.

Now suppose instead that $q<400k^{2}$. Our argument for this case is
essentially the same as for the previous case, except that we use the more
precise form of Proposition 3.2 (since $q$ is now small enough to permit
this). Indeed, Proposition 3.2 yields a set $X\subseteq V_{1}$ with
$|X|=a_{1}\leq n-q$ such that for every $u\in X$ we have $|L_{u}\cap M|\geq
n-a_{1}+(k-1)q$. Let $Z\subseteq V_{1}\setminus X$ have $|Z|=q$. By Lemma 2.5,
applied with $m=0$ and $t=q$, the family $\\{L_{u}(H)\\}_{u\in Z}$ admits a
perfect rainbow matching $M_{rainbow}$. Define $M^{\prime}\subseteq M$ by
$M^{\prime}:=\\{e\in M:e\cap V(M_{rainbow})=\emptyset\\}$, and let $M^{*}$ be
a perfect matching in $K^{k-1}$ with $M^{\prime}\cup M_{rainbow}\subseteq
M^{*}$. Since $|V(M_{rainbow})|=(k-1)|M_{rainbow}|=(k-1)q$, we have for each
$u\in X$ that $|L_{u}(H)\cap M^{*}|\geq|L_{u}(H)\cap M^{\prime}|\geq
n-a_{1}+(k-1)q-(k-1)q=n-a_{1}$. Set $U^{*}=X\cup Z$, and form an auxiliary
bipartite graph $B$ with vertex classes $U^{*}$ and $M^{*}$ in which, for each
$u\in U^{*}$ and $f\in M^{*}$, we have $uf\in E(B)$ if and only if
$\\{u\\}\cup f\in E(H)$. Now consider a subset $S\subseteq U^{*}$. If $|S|\geq
n-a_{1}+1$ then $|N_{B}(S)|=n\geq|S|$ by Proposition 3.1; alternatively, if
$|S|\leq n-a_{1}$ and $S$ contains some $u\in X$ then
$|N_{B}(S)|\geq|N_{B}(u)|\geq n-a_{1}\geq|S|$; finally if $|S|\subseteq Z$
then $|N_{B}(S)|\geq|N_{M_{rainbow}}(S)|=|S|$. We conclude that the graph $B$
satisfies Hall’s criterion, and therefore contains a matching $M_{B}$ of size
$|U^{*}|$; we then have a matching $\\{\\{u\\}\cup f:u\in U^{*},f\in
M^{*},uf\in M_{B}\\}$ in $H$ of size
$|U^{*}|=|X|+|Z|=a_{1}+q=\sum_{i\in[k]}a_{i}$ as required. ∎

##  4\. Concluding Remarks

The main contribution of this paper is to extend Fact 1.1 to the $k$-graph
setting, with the degree condition for graphs being replaced by a codegree
condition for $k$-graphs. Following Pikhurko [33] and Lo and Markström [29],
it would be interesting to investigate lower bounds on the matching number
$\nu(H)$ for $k$-partite $k$-graphs $H$ satisfying analogous minimum
multipartite $\ell$-degree conditions for $\ell<k-1$.

As described in Section 1.2, we see the combination of degree and multiplicity
conditions appearing in Lemma 2.5 as being a natural setting to consider, and
expect that that result should hold for a much wider range of values of $m,q$
and $t$; we think this question is worthy of further attention.

##  5\. Acknowledgements

We thank Alexey Pokrovskiy for helpful discussions in initial stages of the
project, and for communicating Lemma 1.8 to us. We also note that our proof of
Theorem 1.7 – particularly the reformulation in terms of rainbow matchings –
was inspired by Aharoni and Haxell’s generalisation of Hall’s theorem for
hypergraphs [2], though this does not appear in the final version of our
arguments.

For the purpose of open access, the authors have applied a Creative Commons
Attribution (CC BY) licence to any Author Accepted Manuscript version arising
from this submission.

## References

  * [1] R. Aharoni, A. Georgakopoulos, and P. Sprüssel, Perfect matchings in $r$-partite $r$-graphs, European Journal of Combinatorics 30 (2009), 39–42.
  * [2] R. Aharoni and P. Haxell, Hall’s theorem for hypergraphs, Journal of Graph Theory 35 (2000), 83–88.
  * [3] N. Alon, P. Frankl, H. Huang, V. Rödl, A. Ruciński and B. Sudakov, Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels, Journal of Combinatorial Theory, Series A 119 (2012), 1200–1215.
  * [4] A. Asadpour, U. Feige and A. Saberi, Santa Claus meets hypergraph matchings, Approximation, Randomization and Combinatorial Optimization: APPROX-RANDOM 2008, Lecture Notes in Computer Science 5171 (2008), 10–20.
  * [5] B. Bollobás, D. Daykin and P. Erdős, Sets of independent edges of a hypergraph, Quarterly Journal of Mathematics 27 (1976), 25–32.
  * [6] Y. Chang, H. Ge, J. Han and G. Wang, Matching of Given Sizes in Hypergraphs, SIAM Journal on Discrete Mathematics 36 (2022), 2323–2338.
  * [7] A. Czygrinow and V. Kamat, Tight co-degree condition for perfect matchings in 4-graphs, Electronic Journal of Combinatorics 19 (2012), no. 2, P20.
  * [8] D.E. Daykin and R. Häggkvist, Degrees giving independent edges in a hypergraph, Bulletin of the Australian Mathematical Society 23 (1981), 103–109.
  * [9] G.A. Dirac, Some theorems on abstract graphs, Proceedings of the London Mathematical Society 2 (1952), 69–81.
  * [10] J. Edmonds, Paths, trees, and flowers, Canadian Journal of Mathematics 17 (1965), 449–467.
  * [11] P. Hall, _On representatives of subsets_ , Journal of the London Mathematical Society 10 (1935), 26–30.
  * [12] J. Han, Near perfect matchings in $k$-uniform hypergraphs, Combinatorics, Probability and Computing 24 (2015), 723–732.
  * [13] J. Han, Decision problem for perfect matchings in dense k-uniform hypergraphs, Transactions of the American Mathematical Society 369 (2017), 5197–5218.
  * [14] J. Han, Perfect Matchings in Hypergraphs and the Erdős Matching Conjecture, SIAM Journal on Discrete Mathematics 30 (2016), 1351–1357.
  * [15] J. Han, On Perfect Matchings in $k$-Complexes, International Mathematics Research Notices 2021 (2021), 8741–8762.
  * [16] J. Han and A. Treglown, The complexity of perfect matchings and packings in dense hypergraphs, Journal of Combinatorial Theory, Series B 141 (2020), 72–104.
  * [17] J. Han, C. Zang and Y. Zhao, Matchings in $k$-partite $k$-uniform hypergraphs, Journal of Graph Theory 95 (2020), 34–58.
  * [18] H. Hàn, Y. Person and M. Schacht, On Perfect Matchings in Uniform Hypergraphs with Large Minimum Vertex Degree, SIAM Journal on Discrete Mathematics 23 (2009), 732–748.
  * [19] R.M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, The IBM Research Symposia Series (1972), 85–103.
  * [20] M. Karpiński, A. Ruciński and E. Szymańska, The complexity of perfect matching problems on dense hypergraphs, Algorithms and Computation: ISAAC 2009, Lecture Notes in Computer Science 5878 (2009), 626–636.
  * [21] P. Keevash, F. Knox and R. Mycroft, Polynomial-time perfect matchings in dense hypergraphs, Advances in Mathematics 269 (2015), 265–334.
  * [22] P. Keevash and R. Mycroft, A geometric theory for hypergraph matching, Memoirs of the American Mathematical Society 233 (2015), monograph 1098.
  * [23] I. Khan, Perfect Matching in 3 uniform hypergraphs with large vertex degree, SIAM Journal on Discrete Mathematics 27 (2013), 1021–1039.
  * [24] I. Khan, Perfect matchings in 4-uniform hypergraphs, Journal of Combinatorial Theory, Series B 116 (2016), 333–366.
  * [25] D. Kühn and D. Osthus, Matchings in hypergraphs of large minimum degree, Journal of Graph Theory 51 (2006), 269–280.
  * [26] D. Kühn and D. Osthus, Embedding large subgraphs into dense graphs, Surveys in Combinatorics 2009, London Mathematical Society Lecture Note Series 365 (2009), 137–167.
  * [27] D. Kühn, D. Osthus and T. Townsend, Fractional and integer matchings in uniform hypergraphs, European Journal of Combinatorics 38 (2014), 83–96.
  * [28] D. Kühn, D. Osthus and A. Treglown, Matchings in 3-uniform hypergraphs, Journal of Combinatorial Theory, Series B 103 (2013), 291–305.
  * [29] A. Lo and K.Markström, Perfect matchings in $3$-partite $3$-uniform hypergraphs, Journal of Combinatorial Theory, Series A 127 (2014), 22–57.
  * [30] H. Lu, Y. Wang and X. Yu, Almost perfect matchings in $k$-partite $k$-graphs, SIAM Journal on Discrete Mathematics 32 (2018), 522–533.
  * [31] H. Lu, X. Yu and X. Yuan, Nearly Perfect Matchings in Uniform Hypergraphs, SIAM Journal on Discrete Mathematics 35 (2021), 1022–1049.
  * [32] K. Markström and A. Ruciński, Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees, European Journal of Combinatorics 32 (2011), 677–687.
  * [33] O. Pikhurko, Perfect matchings and $K^{3}_{4}$-tilings in hypergraphs of large codegree, Graphs and Combinatorics 24 (2008), 391–404.
  * [34] V. Rödl and A. Ruciński, Dirac-type questions for hypergraphs — a survey (or more problems for Endre to solve), An Irregular Mind, Bolyai Society Mathematical Studies 21 (2010), 561–590.
  * [35] V. Rödl, A. Ruciński and E. Szemerédi, A Dirac-Type Theorem for 3-Uniform Hypergraphs, Combinatorics, Probability and Computing 15 (2006), 229–251.
  * [36] V. Rödl, A. Ruciński and E. Szemerédi, Perfect matchings in uniform hypergraphs with large minimum degree, European Journal of Combinatorics 27 (2006), 1333–1349.
  * [37] E. Szymańska, The complexity of almost perfect matchings in uniform hypergraphs with high codegree, Combinatorial Algorithms: IWOCA 2009, Lecture Notes in Computer Science 5874 (2009), 438–449.
  * [38] A. Treglown and Y. Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, Journal of Combinatorial Theory, Series A 119 (2012), 1500–1522.
  * [39] W. Tutte, The factorization of linear graphs, Journal of the London Mathematical Society 22 (1947), 107–111.
  * [40] Y. Zhao, Recent advances on Dirac-type problems for hypergraphs, Recent Trends in Combinatorics, The IMA Volumes in Mathematics and its Applications 159 (2016), 145–165.


# Computational Choreography using Human Motion Synthesis

Patrick Perrine
California Polytechnic State University
1 Grand Avenue, San Luis Obispo, CA 93407
<EMAIL_ADDRESS>Trevor Kirkby
<EMAIL_ADDRESS>
###### Abstract

Should deep learning models be trained to analyze human performance art? To
help answer this question, we explore an application of deep neural networks
to synthesize artistic human motion. Problem tasks in human motion synthesis
can include predicting the motions of humans in-the-wild, as well as
generating new sequences of motions based on said predictions. We will discuss
the potential of a less traditional application, where learning models are
applied to predicting dance movements. There have been notable, recent efforts
to analyze dance movements in a computational light, such as the Everybody
Dance Now (EDN) learning model and a recent Cal Poly master’s thesis, Take The
Lead (TTL). We have effectively combined these two works along with our own
deep neural network to produce a new system for dance motion prediction,
image-to-image translation, and video generation.

##  1 Introduction

Human motion synthesis involves digitally extracting the geometry of the human
body for analysis or use in software applications. This area has been explored
using a variety of methodologies for a multitude of application areas. Some
current research themes involve using deep neural networks for predicting
human motion [17], generating graphics for augmented reality [3], and motion
transfer [11].

In this research we intended to accomplish the following:

  * •

Reproduce the results of relevant research in academia. More specifically,
implement an instance of OpenPose [10] for processing human skeletons from
video and Everybody Dance Now [11] for video generation.

  * •

Design a custom deep learning model for human motion prediction, specifically
for performance art.

  * •

Apply a new dataset to all these models.

This model could be used by dance choreographers to analyze their dance
pieces. Artists sometimes are concerned with subverting or reinforcing
expectations, so being able to measure the predictability of their performance
could allow them greater control to work to be more predictable or less
predictable in their movements. This model could also have applications in
computer graphics, animation, and mixed reality. Being able to generate new
human motion and a subsequent video of predicted motion could ease the
processing of human avatars.

##  2 Background

To understand human motion synthesis, one must understand the principles of
computer vision. This field is concerned with utilizing digital cameras as
“eyes” for computer programs to “see.” If one has some intuition of computer
graphics, one can conceptualize computer vision as inverse computer graphics
[6]. Whereas work in computer graphics is concerned with generating visuals
based on data, computer vision is about extracting data from visuals. Despite
the two fields being logical complements to each other, there has been much
cross-fertilization in research for vision and graphics over decades. This has
resulted in various sub-disciplines such as human motion synthesis, which has
conceptual roots as early as the mid-1970’s [22]. Studies in human motion saw
a significant surge in the late 1990’s/early 2000’s [2] and have been
consistently present in computer vision literature since.

Being familiar with various machine learning models, such as Recurrent Neural
Networks (RNNs) [29], Convolutional Neural Networks (CNNs) [23], and
Generative Adversarial Networks (GANs) [13] are often required to understand
the architecture of these models.

Generative Adversarial Networks are systems in which two distinct neural
networks are trained in competition. One of them optimizes towards
distinguishing genuine and synthesized examples from a dataset, while the
other optimizes towards synthesizing convincing examples to fool the first
network [13]. Generative adversarial networks have been used successfully to
create or transform images [42], and more specifically for generating human
motion [11].

##  3 Related Work

There have been various approaches to understanding human motion in digital
form. A common approach is to intake video of humans performing actions,
generate representations of their bodies, and then perform motion prediction
[4, 7, 8, 9, 17, 18, 19, 20, 24, 25, 27, 28, 31, 32, 36, 37, 40], motion
transfer [11, 41], generate more sequences of motion [5], or various forms of
analysis [15]. For the latter operations described, deep neural networks have
commonly been applied, sometimes in conjunction with the popular OpenPose
framework [10].

There has also been recent interest in human motion forecasting [26, 34],
which focuses on predicting human movement trajectories from a distant, top-
down perspective. Interest in prediction methods have also lent themselves to
head position prediction for virtual reality [3].

Figure 1: Our video-to-video system. We can intake 2D videos of human motion
and output predicted sequences of motion, as well as output synthesized video
of said predicted sequences.

##  4 Data Acquisition

Data was obtained primarily from the Take The Lead Dataset, which was
published as part of a Cal Poly Master’s Thesis [14]. This data was originally
collated from a publicly available repository: videos of dance were that were
publicly posted on YouTube. Videos were downloaded and labeled by hand to
reflect several different genres of dance. We acknowledge that there may exist
some noise within the image data, which could affect results drawn from models
trained on such data. Sample data from the Everybody Dance Now system was also
used as a reference point. This includes footage of collaborators in the
Everybody Dance Now project performing basic human motions optimized targeted
for testing the Everybody Dance Now system. This sample data is linked
publicly in the associated repository:
https://github.com/carolineec/EverybodyDanceNow. There were no human subjects
involved within the course of this work.

As with virtually all machine learning systems, the products of our system may
inherit biases present in the data the system is taught with. This issue has
continued to be addressed within the academic communities of machine learning
[16]. The potential of bias is difficult to entirely eliminate from machine
learning, and it is important to consider the potential biases introduced
through datasets. A significant mitigating factor of bias in this work is that
all video of humans is preprocessed down to simple stick figures, which only
convey information about a subject’s physical pose. Since our system is only
aware of humans as stick figures, we believe it is difficult for our system to
inherit biases from information such as race, gender, et cetera. The datasets
we used were also acquired from two existing works that were vetted prior to
publication. We suggest the investigation of ethical frameworks when creating
new datasets to be released publicly [30].

##  5 System Design

Our system (see Figure 1) learns from the contents of YouTube videos of
dancing, obtained from Take The Lead. These are stored as sequences of PNG
images for each video frame. From there, OpenPose is used to estimate the
human poses in each frame, creating JSON representations that give two-
dimensional coordinates for various key points (head, chest, shoulders, et
cetera). At this point, the data may be used in two separate models: Everybody
Dance Now and the custom keypoint prediction LSTM network.

To make Everybody Dance Now work for videos scraped from YouTube, which often
contain multiple people, the OpenPose JSON files are altered to only keep
track of the poses for a single person in each video (using the closeness of
the keypoints of consecutive frames to infer which person is which between
frames). Then a data preparation script provided in the EDN repository is used
to convert the JSON files to images of stick figures, which are provided as
inputs to EDN’s conditional GAN. EDN trains from footage of a specific person
performing movements and then can create footage of that same person
performing new movements, based on stick figures of those movements. The
footage is provided as sequential image frames, which are resized to a correct
aspect ratio and then combined into a single video.

The custom keypoint predicting LSTM network, (KP-RNN, seen in Figure 2)
accepts a sequence of poses as input (stored as 50 numbers, which are the
(x,y) coordinates of the 25 keypoints created by OpenPose to model the
position of a single person). It has several LSTM layers and some densely
connected layers at the end, and for the most part is a pretty conventional
sequential network that uses stochastic gradient descent to optimize mean
squared error. The output is the prediction for the person’s pose in the next
frame of the video, again represented as 50 numbers. It should be noted that
the predictions of this network can be used to generate a sequence of poses,
which can then be provided as an input to Everybody Dance Now as poses to
generate a new video based on. There was some fine-tuning of the architectural
design of KP-RNN, but not so much as to overfit our training data.

Figure 2: Our Keypoint Recurrent Neural Network Architecture (KP-RNN).

### Implementation

This system was set up on an instance of Google Colab Pro running with a Tesla
P100 GPU as a development environment. The system is implemented using
primarily Python and Bash, and both Everybody Dance Now and the custom
architecure KP-RNN are implemented using Tensorflow [1] and Keras [12]. The
creation of skeleton pose estimates is accomplished using the OpenPose project
compiled from source. Results are visualized with Tensorboard and Python
matplotlib, and pre-processed into video using Python Image Library and the
FFMPEG command-line interface.

##  6 Testing and Validation

For the KP-RNN architecture, evaluation is mainly scored the same as the loss
function, namely mean squared error between the predicted set of key point
coordinates and the actual set of key point coordinates.

$\textrm{Mean Squared
Error}=\frac{1}{n}\Big{(}\sum_{i=0}^{n}(\textrm{predicted}_{i}-\textrm{expected}_{i})^{2}\Big{)}$

KP-RNN is also able to generate a sequence of human movement which may be
evaluated qualitatively.

For EDN, there are several relevant evaluation metrics available based on
scoring the difference between the generated video and the actual video. The
first such metric is the feature matching loss (figures 4(a) and 5(a)).
Feature matching is calculated by running both the generated image and the
actual image for a given pose through the image discriminator, comparing the
similarities between the vector outputs of intermediate layers in the
discriminator network, and optimizing to improve this similarity [38]. The
second metric is perceptual reconstruction loss (figures 4(b) and 5(b)), which
takes a very similar approach, except instead of using the intermediate layers
of the GAN discriminator, it looks at the intermediate layers of a completely
different image recognition architecture, specifically VGG19 [35]. Note that
EDN records the difference between intermediate layers rather than the
similarities for this metric, so while a higher value indicates better
accuracy for feature matching, the opposite is true for perceptual
reconstruction loss.

The actual generator and discriminator loss functions are comparatively not
useful for the purposes of evaluation, because by construction they exist in a
zero-sum game and in a successful GAN they will remain approximately evenly
matched. EDN also produces video outputs, which may be evaluated
qualitatively. See figures 6(b) and 7(b) for sample frames from the generated
video, based on the inputs in figures 6(a) and 7(a). Figure 6(a) is from the
Everybody Dance Now demonstration dataset, and uses a more complex skeleton
figure with individual keypoints for hands and face, whereas figure 7(a) is
from the Take The Lead dataset, and uses a simplified skeleton with fewer
keypoints.

Figure 3: KP-RNN training error over time. Accuracy at 1000 epochs was 0.94579

(a) EDN Feature Matching with EDN Data

(b) EDN Perceptual Reconstruction Loss with EDN Data

Figure 4:

(a) EDN Feature Matching with New Data

(b) EDN Perceptual Reconstruction Loss with New Data

Figure 5:

(a) Skeleton Input

(b) Synthesized Image

Figure 6:

(a) Skeleton Input

(b) Synthesized Image

Figure 7:

### Project Goal Evaluation

Here is how we accomplished our original goals, along with some more technical
details:

  * •

Reproduce the results of relevant research in academia.

This was mostly accomplished. However, for EDN, we found an issue where the
model does not recognize more than one person. We now have a functional
solution in which we can pre-process new 2D videos of multiple people and
focus on a single person throughout the video sequence. This complies with the
limitation of EDN being only able to process one person’s sequence.

  * •

Design a custom deep learning model for human motion prediction, specifically
tailored for performance art.

We now have our own LSTM-based architecture, KP-RNN, for predicting human
motion sequences, which we developed in Google Colab. As for the hardware we
are used to develop the system, we have been using an instance of Google Colab
Pro. Our code is publicly available on this GitHub repository:
https://github.com/patrickrperrine/comp-choreo

  * •

Apply a new dataset to all these models.

We were interested in creating a new dataset of theatrical performances to be
used for prediction along with our existing dance dataset. We found this to be
difficult and too time-constrained for the scope of this project.

##  7 Future Work

Through our literature search, we ended up exploring a number of different
types of deep learning models, from GANs to RNNs to various hybrids. We feel
that this was acceptable for a class research project, but we are aware that
in more dedicated research projects outside of coursework, this is not always
the best approach for researching models. It can be difficult to compare
models to one another when they have very different architectures and even
different end results. This project allowed us to learn this first-hand, so
that we will be more targeted in our future research.

We found that creating a new, usable dataset can be rather difficult.
Acquiring the theatrical performance data as originally proposed could be a
fruitful endeavor, as described repeatedly through the project’s
documentation. Having more computational power to try to build larger, custom
architectures could lead to novel results in human motion prediction.
Exploring newer, related topics such as human trajectory prediction [34] using
transfer learning could be of interest.

##  8 Conclusions

This project is a relevant exploration into deep learning applications, as our
system contains a deep learning architecture. Our system is also a multiagent
system [39], in which it uses multiple intelligent agents, including a
predictor agent and the two GAN agents (generator and discriminator.) All
three agents interact with each other in some notable fashion, such as the
zero-sum game that the generator and discriminator [13]. They all either
collaborate or cooperate in their interactions and are not concerned with
resource management. All agents in this system are also implemented as
learning agents [33].

In our exploration of various models and other academic works such as
datasets, we found issues in the legality in recreating their work. More
specifically, we attempted to explore the creation of the Human 3.6M dataset
[21], which is very popular in human motion prediction models [5]. This
dataset is not in the same format as the keypoint structures of human motion
as OpenPose, leading to incompatibility with our Take the Lead dataset and
models other than EDN. We attempted to contact the creators of Human 3.6M to
learn about how they parsed 2D video data into their result, so that we could
parse Take the Lead dance data into that same format to be usable by various
models. We ran into an issue where it seemed that this conversion process was
proprietary and/or inaccessible to students with limited resources.

## Acknowledgements

This work was partially supported by a Cal Poly Graduate Assistant Fellowship
to Patrick Perrine. We thank Professors Franz Kurfess and Jonathan Ventura for
their support of this work.

## References

  * [1] Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al.  Tensorflow: A system for large-scale machine learning.  In 12th USENIX symposium on operating systems design and implementation (OSDI 16), pages 265–283, 2016.
  * [2] Jake K Aggarwal and Quin Cai.  Human motion analysis: A review.  Computer vision and image understanding, 73(3):428–440, 1999.
  * [3] Abdenour Amamra.  Smooth head tracking for virtual reality applications.  Signal, Image and Video Processing, 11(3):479–486, 2017.
  * [4] Emad Barsoum, John Kender, and Zicheng Liu.  HP-GAN: Probabilistic 3d human motion prediction via gan.  In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pages 1418–1427, 2018.
  * [5] Neeraj Battan, Yudhik Agrawal, Sai Soorya Rao, Aman Goel, and Avinash Sharma.  Glocalnet: Class-aware long-term human motion synthesis.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 879–888, 2021.
  * [6] Bruce G Baumgart.  A polyhedron representation for computer vision.  In Proceedings of the May 19-22, 1975, national computer conference and exposition, pages 589–596, 1975.
  * [7] Samy Bengio, Oriol Vinyals, Navdeep Jaitly, and Noam Shazeer.  Scheduled sampling for sequence prediction with recurrent neural networks.  arXiv preprint arXiv:1506.03099, 2015.
  * [8] Judith Butepage, Michael J Black, Danica Kragic, and Hedvig Kjellstrom.  Deep representation learning for human motion prediction and classification.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6158–6166, 2017.
  * [9] Haoye Cai, Chunyan Bai, Yu-Wing Tai, and Chi-Keung Tang.  Deep video generation, prediction and completion of human action sequences.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 366–382, 2018.
  * [10] Zhe Cao, Gines Hidalgo, Tomas Simon, Shih-En Wei, and Yaser Sheikh.  Openpose: realtime multi-person 2d pose estimation using part affinity fields.  IEEE transactions on pattern analysis and machine intelligence, 43(1):172–186, 2019.
  * [11] Caroline Chan, Shiry Ginosar, Tinghui Zhou, and Alexei A Efros.  Everybody dance now.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5933–5942, 2019.
  * [12] Francois Chollet et al.  Keras: The python deep learning library.  Astrophysics Source Code Library, pages ascl–1806, 2018.
  * [13] Antonia Creswell, Tom White, Vincent Dumoulin, Kai Arulkumaran, Biswa Sengupta, and Anil A Bharath.  Generative adversarial networks: An overview.  IEEE Signal Processing Magazine, 35(1):53–65, 2018.
  * [14] Ty Farris.  Take The Lead: Toward a virtual video dance partner.  Cal Poly Digital Commons, 2021.
  * [15] David A Forsyth, Okan Arikan, Leslie Ikemoto, Deva Ramanan, and James O’Brien.  Computational studies of human motion: Tracking and motion synthesis.  Foundations and Trends in Computer Graphics and Vision, 2006.
  * [16] Andre Fu, Elisa Ding, Mahdi S Hosseini, and Konstantinos N Plataniotis.  P4ai: Approaching ai ethics through principlism.  In Neural Information Processing Systems 2021 Workshops, 2021.
  * [17] Partha Ghosh, Jie Song, Emre Aksan, and Otmar Hilliges.  Learning human motion models for long-term predictions.  In 2017 International Conference on 3D Vision (3DV), pages 458–466. IEEE, 2017.
  * [18] Anand Gopalakrishnan, Ankur Mali, Dan Kifer, Lee Giles, and Alexander G Ororbia.  A neural temporal model for human motion prediction.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12116–12125, 2019.
  * [19] Chunzhi Gu, Yan Zhao, and Chao Zhang.  Learning to predict diverse human motions from a single image via mixture density networks.  arXiv preprint arXiv:2109.05776, 2021.
  * [20] Luca Hermes, Barbara Hammer, and Malte Schilling.  Application of graph convolutions in a lightweight model for skeletal human motion forecasting.  arXiv preprint arXiv:2110.04810, 2021.
  * [21] Catalin Ionescu, Dragos Papava, Vlad Olaru, and Cristian Sminchisescu.  Human3. 6m: Large scale datasets and predictive methods for 3d human sensing in natural environments.  IEEE transactions on pattern analysis and machine intelligence, 36(7):1325–1339, 2013.
  * [22] Gunnar Johansson.  Visual motion perception.  Scientific American, 232(6):76–89, 1975.
  * [23] Yann LeCun, Yoshua Bengio, et al.  Convolutional networks for images, speech, and time series.  The handbook of brain theory and neural networks, 3361(10):1995, 1995.
  * [24] Maosen Li, Siheng Chen, Yangheng Zhao, Ya Zhang, Yanfeng Wang, and Qi Tian.  Multiscale spatio-temporal graph neural networks for 3d skeleton-based motion prediction.  IEEE Transactions on Image Processing, 30:7760–7775, 2021.
  * [25] Zimo Li, Yi Zhou, Shuangjiu Xiao, Chong He, Zeng Huang, and Hao Li.  Auto-conditioned recurrent networks for extended complex human motion synthesis.  arXiv preprint arXiv:1707.05363, 2017.
  * [26] Karttikeya Mangalam, Yang An, Harshayu Girase, and Jitendra Malik.  From goals, waypoints and paths to long term human trajectory forecasting.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 15233–15242, 2021.
  * [27] Wei Mao, Miaomiao Liu, and Mathieu Salzmann.  Generating smooth pose sequences for diverse human motion prediction.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 13309–13318, 2021.
  * [28] Angel Martinez-Gonzalez, Michael Villamizar, and Jean-Marc Odobez.  Pose transformers (potr): Human motion prediction with non-autoregressive transformers.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2276–2284, 2021.
  * [29] Larry Medsker and Lakhmi C Jain.  Recurrent neural networks: design and applications.  CRC press, 1999.
  * [30] Margaret Mitchell, Simone Wu, Andrew Zaldivar, Parker Barnes, Lucy Vasserman, Ben Hutchinson, Elena Spitzer, Inioluwa Deborah Raji, and Timnit Gebru.  Model cards for model reporting.  In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 220–229, 2019.
  * [31] Abduallah Mohamed, Huancheng Chen, Zhangyang Wang, and Christian Claudel.  Skeleton-graph: Long-term 3d motion prediction from 2d observations using deep spatio-temporal graph cnns.  arXiv preprint arXiv:2109.10257, 2021.
  * [32] Hee-Seung Moon and Jiwon Seo.  Fast user adaptation for human motion prediction in physical human–robot interaction.  IEEE Robotics and Automation Letters, 7(1):120–127, 2021.
  * [33] Stuart Russell and Peter Norvig.  Artificial Intelligence: A Modern Approach.  Pearson, 2021.
  * [34] Nasim Shafiee, Taskin Padir, and Ehsan Elhamifar.  Introvert: Human trajectory prediction via conditional 3d attention.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16815–16825, 2021.
  * [35] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [36] Ruben Villegas, Dumitru Erhan, Honglak Lee, et al.  Hierarchical long-term video prediction without supervision.  In International Conference on Machine Learning, pages 6038–6046. PMLR, 2018.
  * [37] Chenxi Wang, Yunfeng Wang, Zixuan Huang, and Zhiwen Chen.  Simple baseline for single human motion forecasting.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2260–2265, 2021.
  * [38] Ting-Chun Wang, Ming-Yu Liu, Jun-Yan Zhu, Andrew Tao, Jan Kautz, and Bryan Catanzaro.  High-resolution image synthesis and semantic manipulation with conditional gans.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8798–8807, 2018.
  * [39] Michael Wooldridge.  An introduction to multiagent systems.  John wiley & sons, 2009.
  * [40] Mohammad Samin Yasar and Tariq Iqbal.  Improving human motion prediction through continual learning.  arXiv preprint arXiv:2107.00544, 2021.
  * [41] Dongsheng Zhou, Chongyang Guo, Rui Liu, Chao Che, Deyun Yang, Qiang Zhang, and Xiaopeng Wei.  Hierarchical learning recurrent neural networks for 3d motion synthesis.  International Journal of Machine Learning and Cybernetics, pages 1–13, 2021.
  * [42] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In Proceedings of the IEEE international conference on computer vision, pages 2223–2232, 2017.