Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu. Issue 3 (28th November 2020)

• Record Type: Journal Article
• Authors: Han, Jie; Morris, Patrick; Treglown, Andrew
• Is Part Of: Random structures & algorithms. Volume 58:Issue 3(2021)
• Page Start: 480
• Page End: 516
• Publication Date: 2020-11-28
• Subjects: clique tilings -- random graphs -- randomly perturbed structures; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20981
• Languages: English
• ISSNs: 1042-9832

Abstract

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 [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 K r ‐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 K r ‐tiling).