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

Abstract

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\mathrm{mod}k$. This special case answers a question of Rödl and Ruciński and was independently obtained by Lu, Wang, and Yu. The proof of Lu, Wang, and Yu closely follows the approach of Han [Combin. Probab. Comput. 24 (2015), 723--732] by using the absorbing method and considering an extremal case. In contrast, our result is more general and its proof is thus more involved: it uses a more complex absorbing method and deals with two extremal cases.

17 pages, 0 figure