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

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 [7] where one starts with a dense graph and then adds m random edges to it. Specifically, given any fixed (Formula presented.) we determine how many random edges one must add to an n-vertex graph G of minimum degree (Formula presented.) to ensure that, asymptotically almost surely, the resulting graph contains a perfect K_r-tiling. As one increases (Formula presented.) 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 [25] (which resolves the purely random case, that is, (Formula presented.)) and that of Hajnal and Szemerédi [18] (which demonstrates that for (Formula presented.) the initial graph already houses the desired perfect K_r-tiling).