A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs

Source abstract

A perfect K t -matching in a graph G is a spanning subgraph consisting of vertex-disjoint copies of K t . A classic theorem of Hajnal and Szemerédi states that if G is a graph of order n with minimum degree δ( G ) ≥ ( t − 1) n / t and t | n , then G contains a perfect K t -matching. Let G be a t -partite graph with vertex classes V 1 , …, V t each of size n . We show that, for any γ > 0, if every vertex x ∈ V i is joined to at least $\bigl ((t-1)/t + \gamma \bigr )n$ vertices of V j for each j ≠ i , then G contains a perfect K t -matching, provided n is large enough. Thus, we verify a conjecture of Fischer [6] asymptotically. Furthermore, we consider a generalization to hypergraphs in terms of the codegree.