{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T13:42:08Z","timestamp":1648906928584},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2017,8,14]],"date-time":"2017-08-14T00:00:00Z","timestamp":1502668800000},"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":[[2018,3]]},"abstract":"<jats:p>Recently there has been much interest in studying random graph analogues of well-known classical results in extremal graph theory. Here we follow this trend and investigate the structure of triangle-free subgraphs of <jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>, <jats:italic>p<\/jats:italic>) with high minimum degree. We prove that asymptotically almost surely each triangle-free spanning subgraph of <jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>, <jats:italic>p<\/jats:italic>) with minimum degree at least (2\/5 + <jats:italic>o<\/jats:italic>(1))<jats:italic>pn<\/jats:italic> is (<jats:italic>p<\/jats:italic><jats:sup>\u22121<\/jats:sup><jats:italic>n<\/jats:italic>)-close to bipartite, and each spanning triangle-free subgraph of <jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>, <jats:italic>p<\/jats:italic>) with minimum degree at least (1\/3 + \u03f5)<jats:italic>pn<\/jats:italic> is <jats:italic>O<\/jats:italic>(<jats:italic>p<\/jats:italic><jats:sup>\u22121<\/jats:sup><jats:italic>n<\/jats:italic>)-close to <jats:italic>r<\/jats:italic>-partite for some <jats:italic>r<\/jats:italic> = <jats:italic>r<\/jats:italic>(\u03f5). These are random graph analogues of a result by Andr\u00e1sfai, Erd\u0151s and S\u00f3s (<jats:italic>Discrete Math.<\/jats:italic><jats:bold>8<\/jats:bold> (1974), 205\u2013218), and a result by Thomassen (<jats:italic>Combinatorica<\/jats:italic><jats:bold>22<\/jats:bold> (2002), 591\u2013596). We also show that our results are best possible up to a constant factor.<\/jats:p>","DOI":"10.1017\/s0963548317000219","type":"journal-article","created":{"date-parts":[[2017,8,14]],"date-time":"2017-08-14T02:29:38Z","timestamp":1502677778000},"page":"141-161","source":"Crossref","is-referenced-by-count":0,"title":["Triangle-Free Subgraphs of Random Graphs"],"prefix":"10.1017","volume":"27","author":[{"given":"PETER","family":"ALLEN","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JULIA","family":"B\u00d6TTCHER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YOSHIHARU","family":"KOHAYAKAWA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BARNABY","family":"ROBERTS","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2017,8,14]]},"reference":[{"key":"S0963548317000219_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2012.11.016"},{"key":"S0963548317000219_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548317000219_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90133-2"},{"key":"S0963548317000219_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-002-0009-5"},{"key":"S0963548317000219_ref7","unstructured":"Brandt S. and Thomass\u00e9 S. Dense triangle-free graphs are four colorable: A solution to the Erd\u0151s-Simonovits problem. J. Combin. Theory Ser. B, to appear."},{"key":"S0963548317000219_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-014-0562-8"},{"key":"S0963548317000219_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60539-0_16"},{"key":"S0963548317000219_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200906"},{"key":"S0963548317000219_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90126-X"},{"key":"S0963548317000219_ref3","unstructured":"Allen P. , B\u00f6ttcher J. , H\u00e0n H. , Kohayakawa Y. and Person Y. (2016) Blow-up lemmas for sparse graphs. arXiv:1612.00622"},{"key":"S0963548317000219_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-014-1120-1"},{"key":"S0963548317000219_ref5","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2014-00816-X"},{"key":"S0963548317000219_ref6","article-title":"A three-colour problem","volume":"9","author":"Descartes","year":"1947","journal-title":"Eureka"},{"key":"S0963548317000219_ref8","first-page":"303","article-title":"Combinatorial theorems relative to a random set. In","volume":"4","author":"Conlon","year":"2014","journal-title":"Proceedings of the International Congress of Mathematicians."},{"key":"S0963548317000219_ref1","unstructured":"Allen P. , B\u00f6ttcher J. , Ehrenm\u00fcller J. and Taraz A. (2016) The Bandwidth Theorem in sparse graphs. arXiv:1612.00661"},{"key":"S0963548317000219_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.01.004"},{"key":"S0963548317000219_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20535"},{"key":"S0963548317000219_ref17","first-page":"60","article-title":"Problem 28","volume":"10","author":"Mantel","year":"1907","journal-title":"Wiskundige Opgaven"},{"key":"S0963548317000219_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-010-0994-x"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548317000219","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,14]],"date-time":"2019-04-14T22:55:33Z","timestamp":1555282533000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548317000219\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,14]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["S0963548317000219"],"URL":"https:\/\/doi.org\/10.1017\/s0963548317000219","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,14]]}}}