A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs

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 $\delta (G)\ge (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 if every vertex $x\in V_i$ is joined to at least $((t-1)/t+\gamma )n$ vertices of $V_j$ for $i\ne j$, then $G$ contains a perfect $K_t$-matching, thus verifying a conjecture of Fisher asymptotically. Furthermore, we consider a generalisation to hypergraphs in terms of the codegree.

includes minor revisions, accepted for publication in Combinatorics Probability and Computing

References in corpus (6)

• Perfect matchings in r-partite r-graphs
• A Multipartite Hajnal-Szemerédi Theorem
• $F$-factors in hypergraphs via absorption
• Approximate Multipartite Version of the Hajnal--Szemerédi Theorem
• Perfect matchings in 3-partite 3-uniform hypergraphs
• On multipartite Hajnal-Szemerédi theorems

Cited by in corpus (2)

• A Multipartite Hajnal-Szemerédi Theorem
• On multipartite Hajnal-Szemerédi theorems