A robust version of the multipartite Hajnal--Szemerédi theorem

Abstract

In this note we show the following strengthening of a multipartite version of the Hajnal--Szemerédi theorem. For an integer $r\ge 3$ and $\gamma >0$, there exists a constant $C$ such that if $p\ge C{n}^{-2/r}(\log n{)}^{1/\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$ and $G$ is a balanced $r$-partite graph with each vertex class of size $n$ and ${\delta }^{\ast }(G)\ge (1-1/r+\gamma )n$, then with high probability the random subgraph $G(p)$ of $G$ contains a $K_r$-factor. We also use it to derive corresponding transversal versions.

13 pages