{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T09:14:03Z","timestamp":1655370843536},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2021,12,13]],"date-time":"2021-12-13T00:00:00Z","timestamp":1639353600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The bandwidth theorem of B\u00f6ttcher, Schacht and Taraz states that any <jats:italic>n<\/jats:italic>-vertex graph <jats:italic>G<\/jats:italic> with minimum degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000481_inline1.png\" \/><jats:tex-math>\n$\\big(\\tfrac{k-1}{k}+o(1)\\big)n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains all <jats:italic>n<\/jats:italic>-vertex <jats:italic>k<\/jats:italic>-colourable graphs <jats:italic>H<\/jats:italic> with bounded maximum degree and bandwidth <jats:italic>o<\/jats:italic>(<jats:italic>n<\/jats:italic>). Recently, a subset of the authors proved a random graph analogue of this statement: for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000481_inline2.png\" \/><jats:tex-math>\n$p\\gg \\big(\\tfrac{\\log n}{n}\\big)^{1\/\\Delta}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> a.a.s. each spanning subgraph <jats:italic>G<\/jats:italic> of <jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>,<jats:italic>p<\/jats:italic>) with minimum degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000481_inline3.png\" \/><jats:tex-math>\n$\\big(\\tfrac{k-1}{k}+o(1)\\big)pn$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains all <jats:italic>n<\/jats:italic>-vertex <jats:italic>k<\/jats:italic>-colourable graphs <jats:italic>H<\/jats:italic> with maximum degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000481_inline4.png\" \/><jats:tex-math>\n$\\Delta$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, bandwidth <jats:italic>o<\/jats:italic>(<jats:italic>n<\/jats:italic>), and at least <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000481_inline5.png\" \/><jats:tex-math>\n$C p^{-2}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices not contained in any triangle. This restriction on vertices in triangles is necessary, but limiting. In this paper, we consider how it can be avoided. A special case of our main result is that, under the same conditions, if additionally all vertex neighbourhoods in <jats:italic>G<\/jats:italic> contain many copies of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000481_inline6.png\" \/><jats:tex-math>\n$K_\\Delta$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> then we can drop the restriction on <jats:italic>H<\/jats:italic> that <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000481_inline7.png\" \/><jats:tex-math>\n$Cp^{-2}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices should not be in triangles.<\/jats:p>","DOI":"10.1017\/s0963548321000481","type":"journal-article","created":{"date-parts":[[2021,12,13]],"date-time":"2021-12-13T13:44:30Z","timestamp":1639403070000},"page":"598-628","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["A spanning bandwidth theorem in random graphs"],"prefix":"10.1017","volume":"31","author":[{"given":"Peter","family":"Allen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julia","family":"B\u00f6ttcher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julia","family":"Ehrenm\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakob","family":"Schnitzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anusch","family":"Taraz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,12,13]]},"reference":[{"key":"S0963548321000481_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.03.004"},{"key":"S0963548321000481_ref1","doi-asserted-by":"crossref","unstructured":"[1] Allen, P. , B\u00f6ttcher, J. , Ehrenm\u00fcller, J. and Taraz, A. (2020) The bandwidth theorem in sparse graphs. Adv. Comb. Paper No. 6, 60.","DOI":"10.19086\/aic.12849"},{"key":"S0963548321000481_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60539-0_16"},{"key":"S0963548321000481_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107325975.007"},{"key":"S0963548321000481_ref2","unstructured":"[2] Allen, P. , B\u00f6ttcher, J. , H\u00e0n, H. , Kohayakawa, Y. and Person, Y. Blow-up lemmas for sparse graphs. Submitted, arXiv:1612.00622."},{"key":"S0963548321000481_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01626028"},{"key":"S0963548321000481_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548321000481_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00208-008-0268-6"},{"key":"S0963548321000481_ref8","unstructured":"[8] Hajnal, A. and Szemer\u00e9di, E. (1970) Proof of a conjecture of P. Erd\u00f6s. In Combinatorial Theory and its Applications, II (Proc. Colloq., Balatonf\u00fcred, 1969), pp. 601\u2013623."},{"key":"S0963548321000481_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20419"},{"key":"S0963548321000481_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000490"},{"key":"S0963548321000481_ref5","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.69"},{"key":"S0963548321000481_ref6","unstructured":"[6] Fischer, M. , \u0160kori\u0107, N. , Steger, A. and Truji\u0107, M. Triangle resilience of the square of a Hamilton cycle in random graphs. Submitted, arXiv:1809.07534."},{"key":"S0963548321000481_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-22444-0_9"},{"key":"S0963548321000481_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/9781108332699.003"},{"key":"S0963548321000481_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196135"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000481","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T08:44:42Z","timestamp":1655282682000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000481\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,13]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["S0963548321000481"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000481","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,13]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}