Matchings in $k$-partite $k$-uniform Hypergraphs

Jie Han, Chuanyun Zang, Yi Zhao

Published 2016-11-01Version 1

For $k\ge 3$ and $\epsilon>0$, let $H$ be a $k$-partite $k$-graph with parts $V_1,\dots, V_k$ each of size $n$, where $n$ is sufficiently large. Assume that for each $i\in [k]$, every $(k-1)$-set in $\prod_{j\in [k]\setminus \{i\}} V_i$ lies in at least $a_i$ edges, and $a_1\ge a_2\ge \cdots \ge a_k$. We show that if $a_1, a_2\ge \epsilon n$, then $H$ contains a matching of size $\min\{n-1, \sum_{i\in [k]}a_i\}$. In particular, $H$ contains a matching of size $n-1$ if each crossing $(k-1)$-set lies in at least $\lceil n/k \rceil$ edges, or each crossing $(k-1)$-set lies in at least $\lfloor n/k \rfloor$ edges and $n\equiv 1\bmod k$. The former case answers a question of R\"odl and Ruci\'nski and was independently obtained by Lu, Wang, and Yu. Our proof is more involved than the one used by the first author, who proved the non-partite version of the result, and the one by Lu, Wang, and Yu. In particular, we used a more complex absorbing method and deal with two extremal cases separately.