Projects per year
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  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  (which resolves the purely random case, that is, (Formula presented.)) and that of Hajnal and Szemerédi  (which demonstrates that for (Formula presented.) the initial graph already houses the desired perfect K r-tiling).
|Number of pages||37|
|Journal||Random Structures and Algorithms|
|Early online date||28 Nov 2020|
|Publication status||Published - May 2021|
Bibliographical noteFunding 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
© 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
- Computer Graphics and Computer-Aided Design
- Applied Mathematics
FingerprintDive 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.
- 1 Finished
EPSRC Fellowship: Dr Andrew Treglown - Independence in groups, graphs and the integers
Engineering & Physical Science Research Council
1/06/15 → 31/05/18
Project: Research Councils