Tilings in randomly perturbed dense graphs
Research output: Contribution to journal › Article › peer-review
Authors
Colleges, School and Institutes
External organisations
- University of Illinois at Urbana-Champaign
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.
Details
Original language | English |
---|---|
Pages (from-to) | 159-176 |
Number of pages | 18 |
Journal | Combinatorics, Probability and Computing |
Volume | 28 |
Issue number | 2 |
Early online date | 16 Jul 2018 |
Publication status | Published - Mar 2019 |