Tilings in randomly perturbed dense graphs

Jozsef Balogh, Andrew Treglown, Adam Zsolt Wagner

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)
136 Downloads (Pure)

Abstract

A perfect H-tiling in a graph G is a collection of vertex-disjoint copies of a graph H in G that together cover all the vertices in G. In this paper we investigate perfect H-tilings 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 H-tiling 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 H-tilings in dense graphs.

Original languageEnglish
Pages (from-to)159-176
Number of pages18
JournalCombinatorics, Probability and Computing
Volume28
Issue number2
Early online date16 Jul 2018
DOIs
Publication statusPublished - 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.

Cite this