Projects per year
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).
Original language | English |
---|---|
Pages (from-to) | 480-516 |
Number of pages | 37 |
Journal | Random Structures and Algorithms |
Volume | 58 |
Issue number | 3 |
Early online date | 28 Nov 2020 |
DOIs | |
Publication status | Published - 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:
Copyright 2020 Elsevier B.V., All rights reserved.
Keywords
- clique tilings
- random graphs
- randomly perturbed structures
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics
Fingerprint
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.Projects
- 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