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

Jie Han, Patrick Morris, Andrew Treglown

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
136 Downloads (Pure)


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

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

Bibliographical 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 2020 Elsevier B.V., All rights reserved.


  • clique tilings
  • random graphs
  • randomly perturbed structures

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'Tilings in randomly perturbed graphs: bridging the gap between Hajnal-Szemerédi and Johansson-Kahn-Vu'. Together they form a unique fingerprint.

Cite this