2019/04/22 by Han, Jie, Morris, Patrick, Treglown, Andrew · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1904.09930
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 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 (which resolves the purely random case, i.e., α=0) and that of Hajnal and Szemerédi (which demonstrates that for α≥ 1-1/r the initial graph already houses the desired perfect Kr-tiling).