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

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

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 (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).

Bibliographic note

Funding Information: Leverhulme Trust Study Abroad Studentship, Grant/Award Number: SAS‐2017‐052∖9 (P.M.); Engineering and Physical Sciences Research Council (EPSRC),EP/M016641/1 (A.T.) Funding information Publisher Copyright: © 2020 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

Details

Original languageEnglish
Pages (from-to)480-516
Number of pages37
JournalRandom Structures and Algorithms
Volume58
Issue number3
Early online date28 Nov 2020
Publication statusPublished - May 2021

Keywords

  • clique tilings, random graphs, randomly perturbed structures