A GENERALIZATION OF HALL'S THEOREM FOR k-UNIFORM k-PARTITE HYPERGRAPHS

In this paper we prove a generalized version of Hall's theorem in graphs, for hypergraphs. More precisely, let H be a k-uniform k-partite hypergraph with some ordering on parts as V1; V2; : : : ; Vk such that the subhypergraph generated on ∪k􀀀1 i=1 Vi has a unique perfect matching. In this case, we give a necessary and sufficient condition for having a matching of size t = jV1j in H. Some relevant results and counterexamples are given as well.