{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T21:49:19Z","timestamp":1648676959974},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2020,2,4]],"date-time":"2020-02-04T00:00:00Z","timestamp":1580774400000},"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,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:italic>c<\/jats:italic> denote the largest constant such that every <jats:italic>C<\/jats:italic><jats:sub>6<\/jats:sub>-free graph <jats:italic>G<\/jats:italic> contains a bipartite and <jats:italic>C<\/jats:italic><jats:sub>4<\/jats:sub>-free subgraph having a fraction <jats:italic>c<\/jats:italic> of edges of <jats:italic>G<\/jats:italic>. Gy\u0151ri, Kensell and Tompkins showed that 3\/8 \u2a7d <jats:italic>c<\/jats:italic> \u2a7d 2\/5. We prove that <jats:italic>c<\/jats:italic> = 38. More generally, we show that for any <jats:italic>\u03b5<\/jats:italic> &gt; 0, and any integer <jats:italic>k<\/jats:italic> \u2a7e 2, there is a <jats:italic>C<\/jats:italic><jats:sub>2<jats:italic>k<\/jats:italic><\/jats:sub>-free graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000452_inline2.png\" \/><jats:tex-math>\n\n$G'$\n\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> which does not contain a bipartite subgraph of girth greater than 2<jats:italic>k<\/jats:italic> with more than a fraction <jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" position=\"float\" xlink:href=\"S0963548319000452_eqnu1.png\" \/><jats:tex-math>\n$$\\Bigl(1-\\frac{1}{2^{2k-2}}\\Bigr)\\frac{2}{2k-1}(1+\\varepsilon)$$\n<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula> of the edges of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000452_inline3.png\" \/><jats:tex-math>\n\n$G'$\n\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. There also exists a <jats:italic>C<\/jats:italic><jats:sub>2<jats:italic>k<\/jats:italic><\/jats:sub>-free graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000452_inline4.png\" \/><jats:tex-math>\n\n$G''$\n\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> which does not contain a bipartite and <jats:italic>C<\/jats:italic><jats:sub>4<\/jats:sub>-free subgraph with more than a fraction <jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" position=\"float\" xlink:href=\"S0963548319000452_eqnu2.png\" \/><jats:tex-math>\n$$\\Bigl(1-\\frac{1}{2^{k-1}}\\Bigr)\\frac{1}{k-1}(1+\\varepsilon)$$\n<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula> of the edges of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000452_inline5.png\" \/><jats:tex-math>\n\n$G''$\n\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p><jats:p>One of our proofs uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of Erd\u0151s. For any <jats:italic>\u03b5<\/jats:italic> &gt; 0, and any integers <jats:italic>a<\/jats:italic>, <jats:italic>b<\/jats:italic>, <jats:italic>k<\/jats:italic> \u2a7e 2, there exists an <jats:italic>a<\/jats:italic>-uniform hypergraph <jats:italic>H<\/jats:italic> of girth greater than <jats:italic>k<\/jats:italic> which does not contain any <jats:italic>b<\/jats:italic>-colourable subhypergraph with more than a fraction <jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" position=\"float\" xlink:href=\"S0963548319000452_eqnu3.png\" \/><jats:tex-math>\n$$\\Bigl(1-\\frac{1}{b^{a-1}}\\Bigr)(1+\\varepsilon)$$\n<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula> of the hyperedges of <jats:italic>H<\/jats:italic>. We also prove further generalizations of this theorem.<\/jats:p><jats:p>In addition, we give a new and very short proof of a result of K\u00fchn and Osthus, which states that every bipartite <jats:italic>C<\/jats:italic><jats:sub>2<jats:italic>k<\/jats:italic><\/jats:sub>-free graph <jats:italic>G<\/jats:italic> contains a <jats:italic>C<\/jats:italic><jats:sub>4<\/jats:sub>-free subgraph with at least a fraction 1\/(<jats:italic>k<\/jats:italic>\u22121) of the edges of <jats:italic>G<\/jats:italic>. We also answer a question of K\u00fchn and Osthus about <jats:italic>C<\/jats:italic><jats:sub>2<jats:italic>k<\/jats:italic><\/jats:sub>-free graphs obtained by pasting together <jats:italic>C<\/jats:italic><jats:sub>2<jats:italic>l<\/jats:italic><\/jats:sub>\u2019s (with <jats:italic>k<\/jats:italic> &gt;<jats:italic>l<\/jats:italic> \u2a7e 3).<\/jats:p>","DOI":"10.1017\/s0963548319000452","type":"journal-article","created":{"date-parts":[[2020,2,4]],"date-time":"2020-02-04T08:23:33Z","timestamp":1580804613000},"page":"436-454","source":"Crossref","is-referenced-by-count":0,"title":["On subgraphs of <i>C<\/i><sub>2<i>k<\/i><\/sub>-free graphs and a problem of K\u00fchn and Osthus"],"prefix":"10.1017","volume":"29","author":[{"given":"D\u00e1niel","family":"Gr\u00f3sz","sequence":"first","affiliation":[]},{"given":"Abhishek","family":"Methuku","sequence":"additional","affiliation":[]},{"given":"Casey","family":"Tompkins","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,2,4]]},"reference":[{"key":"S0963548319000452_ref12","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1978-0507350-7"},{"key":"S0963548319000452_ref11","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1971.11992886"},{"key":"S0963548319000452_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894680"},{"key":"S0963548319000452_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20048"},{"key":"S0963548319000452_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00184-7"},{"key":"S0963548319000452_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2005.04.011"},{"key":"S0963548319000452_ref1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1966-109-8"},{"key":"S0963548319000452_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.06.008"},{"key":"S0963548319000452_ref8","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548319000452_ref2","first-page":"283","article-title":"Gr\u00e1fok p\u00e1ros k\u00f6r\u00fclj\u00e1r\u00e1s\u00fa r\u00e9szgr\u00e1fjair\u00f3l (On bipartite subgraphs of graphs, in Hungarian)","volume":"18","author":"Erd\u0151s","year":"1967","journal-title":"Mat. Lapok"},{"key":"S0963548319000452_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020444"},{"key":"S0963548319000452_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579234"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000452","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,26]],"date-time":"2020-05-26T10:26:56Z","timestamp":1590488816000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000452\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,4]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["S0963548319000452"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000452","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,4]]}}}