{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T05:27:19Z","timestamp":1767245239484},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T00:00:00Z","timestamp":1564012800000},"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":[[2020,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given graphs <jats:italic>G<\/jats:italic> and <jats:italic>H<\/jats:italic>, a family of vertex-disjoint copies of <jats:italic>H<\/jats:italic> in <jats:italic>G<\/jats:italic> is called an <jats:italic>H-tiling<\/jats:italic>. Conlon, Gowers, Samotij and Schacht showed that for a given graph <jats:italic>H<\/jats:italic> and a constant <jats:italic>\u03b3<\/jats:italic><jats:sub>&gt;0<\/jats:sub>, there exists <jats:italic>C<\/jats:italic><jats:sub>&gt;0<\/jats:sub> such that if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000129_inline1\" \/><jats:tex-math>\n$p \\ge C{n^{ - 1\/{m_2}(H)}}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then asymptotically almost surely every spanning subgraph <jats:italic>G<\/jats:italic> of the random graph \ud835\udca2<jats:sub>(<jats:italic>n, p<\/jats:italic>)<\/jats:sub> with minimum degree at least <jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548319000129_eqn1\" \/><jats:tex-math>\n$\\delta (G) \\ge (1 - \\frac{1}{{{\\chi _{{\\rm{cr}}}}(H)}} + \\gamma )np$\n<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula> contains an <jats:italic>H<\/jats:italic>-tiling that covers all but at most <jats:italic>\u03b3n<\/jats:italic> vertices. Here, <jats:italic>\u03c7<\/jats:italic><jats:sub>cr(<jats:italic>H<\/jats:italic>)<\/jats:sub> denotes the <jats:italic>critical chromatic number<\/jats:italic>, a parameter introduced by Koml\u00f3s, and <jats:italic>m<\/jats:italic><jats:sub>2<\/jats:sub>(<jats:italic>H<\/jats:italic>) is the 2<jats:italic>-density<\/jats:italic> of <jats:italic>H<\/jats:italic>. We show that this theorem can be bootstrapped to obtain an <jats:italic>H<\/jats:italic>-tiling covering all but at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000129_inline2\" \/><jats:tex-math>\n$\\gamma {(C\/p)^{{m_2}(H)}}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices, which is strictly smaller when <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000129_inline1\" \/><jats:tex-math>\n$p \\ge C{n^{ - 1\/{m_2}(H)}}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. In the case where <jats:italic>H<\/jats:italic>\n = <jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub>, this answers the question of Balogh, Lee and Samotij. Furthermore, for an arbitrary graph <jats:italic>H<\/jats:italic> we give an upper bound on <jats:italic>p<\/jats:italic> for which some leftover is unavoidable and a bound on the size of a largest <jats:italic>H<\/jats:italic> -tiling for <jats:italic>p<\/jats:italic> below this value.<\/jats:p>","DOI":"10.1017\/s0963548319000129","type":"journal-article","created":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T03:39:06Z","timestamp":1564025946000},"page":"113-127","source":"Crossref","is-referenced-by-count":4,"title":["On Koml\u00f3s\u2019 tiling theorem in random graphs"],"prefix":"10.1017","volume":"29","author":[{"given":"Rajko","family":"Nenadov","sequence":"first","affiliation":[]},{"given":"Nemanja","family":"\u0160kori\u0107","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,7,25]]},"reference":[{"key":"S0963548319000129_ref4","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0020"},{"key":"S0963548319000129_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-014-1120-1"},{"key":"S0963548319000129_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070014"},{"key":"S0963548319000129_ref22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10091"},{"key":"S0963548319000129_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-014-0562-8"},{"key":"S0963548319000129_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20224"},{"key":"S0963548319000129_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60539-0_16"},{"key":"S0963548319000129_ref11","first-page":"601","volume-title":"Combinatorial Theory and its Applications, II (Proc. Colloq., Balatonf\u00fcred, 1969)","author":"Hajnal","year":"1970"},{"key":"S0963548319000129_ref17","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":"S0963548319000129_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.03.002"},{"key":"S0963548319000129_ref6","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2014-00816-X"},{"key":"S0963548319000129_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02350627"},{"key":"S0963548319000129_ref2","unstructured":"[2] Allen, P. , B\u00f6ttcher, J. , H\u00e0n, H. , Kohayakawa, Y. and Person, Y. (2016) Blow-up lemmas for sparse graphs. arXiv:1612.00622"},{"key":"S0963548319000129_ref9","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u00f6s","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"S0963548319000129_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2015.06.071"},{"key":"S0963548319000129_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21805"},{"key":"S0963548319000129_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107325975.007"},{"key":"S0963548319000129_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000642"},{"key":"S0963548319000129_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2254-3"},{"key":"S0963548319000129_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200906"},{"key":"S0963548319000129_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00279-X"},{"key":"S0963548319000129_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01895727"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,14]],"date-time":"2020-01-14T05:57:08Z","timestamp":1578981428000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000129\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,25]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["S0963548319000129"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000129","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,25]]}}}