{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T04:24:24Z","timestamp":1773980664078,"version":"3.50.1"},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2018,7,16]],"date-time":"2018-07-16T00:00:00Z","timestamp":1531699200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,3]]},"abstract":"<jats:p>A perfect <jats:italic>H<\/jats:italic>-tiling in a graph <jats:italic>G<\/jats:italic> is a collection of vertex-disjoint copies of a graph <jats:italic>H<\/jats:italic> in <jats:italic>G<\/jats:italic> that together cover all the vertices in <jats:italic>G<\/jats:italic>. In this paper we investigate perfect <jats:italic>H<\/jats:italic>-tilings in a random graph model introduced by Bohman, Frieze and Martin [6] in which one starts with a dense graph and then adds <jats:italic>m<\/jats:italic> random edges to it. Specifically, for <jats:italic>any<\/jats:italic> fixed graph <jats:italic>H<\/jats:italic>, 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 <jats:italic>H<\/jats:italic>-tiling with high probability. Our proof utilizes Szemer\u00e9di's Regularity Lemma [29] as well as a special case of a result of Koml\u00f3s [18] concerning almost perfect <jats:italic>H<\/jats:italic>-tilings in dense graphs.<\/jats:p>","DOI":"10.1017\/s0963548318000366","type":"journal-article","created":{"date-parts":[[2018,7,16]],"date-time":"2018-07-16T07:40:30Z","timestamp":1531726830000},"page":"159-176","source":"Crossref","is-referenced-by-count":35,"title":["Tilings in Randomly Perturbed Dense Graphs"],"prefix":"10.1017","volume":"28","author":[{"given":"J\u00d3ZSEF","family":"BALOGH","sequence":"first","affiliation":[]},{"given":"ANDREW","family":"TREGLOWN","sequence":"additional","affiliation":[]},{"given":"ADAM ZSOLT","family":"WAGNER","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,7,16]]},"reference":[{"key":"S0963548318000366_ref30","unstructured":"Treglown A. (2007) The regularity lemma and applications to packings in graphs. MSc thesis, University of Birmingham."},{"key":"S0963548318000366_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90068-6"},{"key":"S0963548318000366_ref26","unstructured":"McDowell A. and Mycroft R. Hamilton \u2113-cycles in randomly perturbed hypergraphs. Submitted."},{"key":"S0963548318000366_ref25","doi-asserted-by":"publisher","DOI":"10.1137\/0404011"},{"key":"S0963548318000366_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2254-3"},{"key":"S0963548318000366_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109651"},{"key":"S0963548318000366_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032910"},{"key":"S0963548318000366_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00279-X"},{"key":"S0963548318000366_ref18","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s004930070020","article-title":"Tiling Tur\u00e1n theorems.","volume":"20","author":"Koml\u00f3s","year":"2000","journal-title":"Combinatorica"},{"key":"S0963548318000366_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20224"},{"key":"S0963548318000366_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548318000366_ref14","unstructured":"Han J. and Zhao Y. Hamiltonicity in randomly perturbed hypergraphs. Submitted."},{"key":"S0963548318000366_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21805"},{"key":"S0963548318000366_ref10","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"S0963548318000366_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894879"},{"key":"S0963548318000366_ref8","unstructured":"B\u00f6ttcher J. , Montgomery R. , Parczyk O. and Person Y. Embedding spanning bounded degree graphs in randomly perturbed graphs. Submitted."},{"key":"S0963548318000366_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10070"},{"key":"S0963548318000366_ref4","unstructured":"Bennett P. , Dudek A. and Frieze A. Adding random edges to create the square of a Hamilton cycle. Submitted."},{"key":"S0963548318000366_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000559"},{"key":"S0963548318000366_ref17","unstructured":"Joos F. and Kim J. Spanning trees in randomly perturbed graphs. Submitted."},{"key":"S0963548318000366_ref13","first-page":"601","volume-title":"Combinatorial Theory and its Applications, II","author":"Hajnal","year":"1970"},{"key":"S0963548318000366_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90141-2"},{"key":"S0963548318000366_ref22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20097"},{"key":"S0963548318000366_ref7","unstructured":"B\u00f6ttcher J. , Han J. , Kohayakawa Y. , Montgomery R. , Parczyk O. and Person Y. Universality for bounded degree spanning trees in randomly perturbed graphs. Submitted."},{"key":"S0963548318000366_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10112"},{"key":"S0963548318000366_ref3","unstructured":"Bedenknecht W. , Han J. , Kohayakawa Y. and Mota G. O. Powers of tight Hamilton cycles in randomly perturbed hypergraphs. Submitted."},{"key":"S0963548318000366_ref29","unstructured":"Szemer\u00e9di E. (1978) Regular partitions of graphs. In Probl\u00e9mes Combinatoires et Th\u00e9orie des Graphes, Vol. 260 of Colloques Internationaux CNRS, pp. 399\u2013401."},{"key":"S0963548318000366_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000079"},{"key":"S0963548318000366_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000196"},{"key":"S0963548318000366_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-008-0268-6"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000366","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T19:02:21Z","timestamp":1555095741000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000366\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,16]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["S0963548318000366"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000366","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,16]]}}}