Projects per year
Abstract
A perfect Htiling in a graph G is a collection of vertexdisjoint copies of a graph H in G that together cover all the vertices in G. In this paper we investigate perfect Htilings in a random graph model introduced by Bohman, Frieze and Martin [6] in which one starts with a dense graph and then adds m random edges to it. Specifically, for any fixed graph H, we determine the number of random edges required to add to an arbitrary graph of linear minimum degree in order to ensure the resulting graph contains a perfect Htiling with high probability. Our proof utilizes Szemerédi's Regularity Lemma [29] as well as a special case of a result of Komlós [18] concerning almost perfect Htilings in dense graphs.
Original language  English 

Pages (fromto)  159176 
Number of pages  18 
Journal  Combinatorics, Probability and Computing 
Volume  28 
Issue number  2 
Early online date  16 Jul 2018 
DOIs  
Publication status  Published  Mar 2019 
ASJC Scopus subject areas
 Theoretical Computer Science
 Statistics and Probability
 Computational Theory and Mathematics
 Applied Mathematics
Fingerprint
Dive into the research topics of 'Tilings in randomly perturbed dense graphs'. 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