Tilings in randomly perturbed dense graphs

Research output: Contribution to journalArticlepeer-review

Standard

Tilings in randomly perturbed dense graphs. / Balogh, Jozsef; Treglown, Andrew; Wagner, Adam Zsolt.

In: Combinatorics, Probability and Computing, Vol. 28, No. 2, 03.2019, p. 159-176.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Balogh, Jozsef ; Treglown, Andrew ; Wagner, Adam Zsolt. / Tilings in randomly perturbed dense graphs. In: Combinatorics, Probability and Computing. 2019 ; Vol. 28, No. 2. pp. 159-176.

Bibtex

@article{39648435f8df48369b0bd23ac651162e,
title = "Tilings in randomly perturbed dense graphs",
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{\'e}di's Regularity Lemma [29] as well as a special case of a result of Koml{\'o}s [18] concerning almost perfect H-tilings in dense graphs.",
author = "Jozsef Balogh and Andrew Treglown and Wagner, {Adam Zsolt}",
year = "2019",
month = mar,
doi = "10.1017/S0963548318000366",
language = "English",
volume = "28",
pages = "159--176",
journal = "Combinatorics, Probability and Computing",
issn = "0963-5483",
publisher = "Cambridge University Press",
number = "2",

}

RIS

TY - JOUR

T1 - Tilings in randomly perturbed dense graphs

AU - Balogh, Jozsef

AU - Treglown, Andrew

AU - Wagner, Adam Zsolt

PY - 2019/3

Y1 - 2019/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85049877762&partnerID=8YFLogxK

U2 - 10.1017/S0963548318000366

DO - 10.1017/S0963548318000366

M3 - Article

VL - 28

SP - 159

EP - 176

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

SN - 0963-5483

IS - 2

ER -