Matching stability for 3-partite 3-uniform hypergraphs

Abstract

Let $n,k,s$ be three integers such that $k\ge 2$ and $n\ge s\ge 1$. Let $H$ be a $k$-partite $k$-uniform hypergraph with $n$ vertices in each class. Aharoni (2017) showed that if $e(H)>(s-1)n^{k-1}$, then $H$ has a matching of size $s$. In this paper, we give a stability result for 3-partite 3-uniform hypergraphs: if $G$ is a $3$-partite $3$-uniform hypergraph with $n\ge 162$ vertices in each class, $e(G)\ge (s-1)n^2+3n-s$ and $G$ contains no matching of size $s+1$, then $G$ has a vertex cover of size $s$. Our bound is also tight.