Tiling randomly perturbed multipartite graphs

Enrique Gomez-Leos; Ryan R. Martin

paper

Tiling randomly perturbed multipartite graphs

arXiv:2504.07284

Abstract

A perfect $K_{r}$ -tiling in a graph $G$ is a collection of vertex-disjoint copies of the graph $K_{r}$ in $G$ that covers all vertices of $G$ . In this paper, we prove that the threshold for the existence of a perfect $K_{r}$ -tiling of a randomly perturbed balanced $r$ -partite graph on $r n$ vertices is $n^{- 2/ r}$ . This result is a multipartite analog of a theorem of Balogh, Treglown, and Wagner and extends our previous result, which was limited to the bipartite setting.