Tilings in randomly perturbed graphs: bridging the gap between Hajnal-Szemerédi and Johansson-Kahn-Vu

Abstract

A perfect $K_r$-tiling in a graph $G$ is a collection of vertex-disjoint copies of $K_r$ that together cover all the vertices in $G$. In this paper we consider perfect $K_r$-tilings in the setting of randomly perturbed graphs; a model introduced by Bohman, Frieze and Martin where one starts with a dense graph and then adds $m$ random edges to it. Specifically, given any fixed $0<\alpha <1-1/r$ we determine how many random edges one must add to an $n$-vertex graph $G$ of minimum degree $\delta (G)\ge \alpha n$ to ensure that, asymptotically almost surely, the resulting graph contains a perfect $K_r$-tiling. As one increases $\alpha$ we demonstrate that the number of random edges required `jumps' at regular intervals, and within these intervals our result is best-possible. This work therefore closes the gap between the seminal work of Johansson, Kahn and Vu (which resolves the purely random case, i.e., $\alpha =0$) and that of Hajnal and Szemerédi (which demonstrates that for $\alpha \ge 1-1/r$ the initial graph already houses the desired perfect $K_r$-tiling).

Final version with 39 pages and 6 figures. Adjusted in accordance to referee reports and to appear in RS&A (Random Structures and Algorithms)