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

Abstract

A perfect Kr-tiling in a graph G is a collection of vertex-disjoint copies of Kr that together cover all the vertices in G. In this paper we consider perfect Kr-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 0 < 𝛼 < 1 − 1∕r we determine how many random edges one must add to an n-vertex graph G of minimum degree 𝛿(G) ≥ 𝛼n to ensure that, asymptotically almost surely, the resulting graph contains a perfect Kr-tiling. As one increases 𝛼 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, 𝛼 = 0) and that of Hajnal and Szemerédi [18] (which demonstrates that for 𝛼 ≥ 1 − 1∕r the initial graph already houses the desired perfect Kr-tiling).