{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T08:29:06Z","timestamp":1699950546777},"reference-count":11,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T00:00:00Z","timestamp":1653868800000},"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,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For a subgraph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline3.png\" \/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of the blow-up of a graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline4.png\" \/><jats:tex-math>\n$F$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, we let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline5.png\" \/><jats:tex-math>\n$\\delta ^*(G)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> be the smallest minimum degree over all of the bipartite subgraphs of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline6.png\" \/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> induced by pairs of parts that correspond to edges of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline7.png\" \/><jats:tex-math>\n$F$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Johansson proved that if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline8.png\" \/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is a spanning subgraph of the blow-up of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline9.png\" \/><jats:tex-math>\n$C_3$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with parts of size <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline10.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline11.png\" \/><jats:tex-math>\n$\\delta ^*(G) \\ge \\frac{2}{3}n + \\sqrt{n}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline12.png\" \/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline13.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertex disjoint triangles, and presented the following conjecture of H\u00e4ggkvist. If <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline14.png\" \/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is a spanning subgraph of the blow-up of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline15.png\" \/><jats:tex-math>\n$C_k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with parts of size <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline16.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline17.png\" \/><jats:tex-math>\n$\\delta ^*(G) \\ge \\left(1 + \\frac 1k\\right)\\frac n2 + 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline18.png\" \/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline19.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertex disjoint copies of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline20.png\" \/><jats:tex-math>\n$C_k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that each <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline21.png\" \/><jats:tex-math>\n$C_k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> intersects each of the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline22.png\" \/><jats:tex-math>\n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> parts exactly once. A similar conjecture was also made by Fischer and the case <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline23.png\" \/><jats:tex-math>\n$k=3$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> was proved for large <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline24.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> by Magyar and Martin.<\/jats:p><jats:p>In this paper, we prove the conjecture of H\u00e4ggkvist asymptotically. We also pose a conjecture which generalises this result by allowing the minimum degree conditions in each bipartite subgraph induced by pairs of parts of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000086_inline25.png\" \/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> to vary. We support this new conjecture by proving the triangle case. This result generalises Johannson\u2019s result asymptotically.<\/jats:p>","DOI":"10.1017\/s0963548322000086","type":"journal-article","created":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T10:06:02Z","timestamp":1653905162000},"page":"1031-1047","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Transversal <i>C<sub>k<\/sub><\/i>-factors in subgraphs of the balanced blow-up of <i>C<sub>k<\/sub><\/i>"],"prefix":"10.1017","volume":"31","author":[{"given":"Beka","family":"Ergemlidze","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theodore","family":"Molla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,5,30]]},"reference":[{"key":"S0963548322000086_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00324-6"},{"key":"S0963548322000086_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.08.019"},{"key":"S0963548322000086_ref5","article-title":"A geometric theory for hypergraph matching","volume":"233","author":"Keevash","year":"2014","journal-title":"Mem. Am. Math. Soc"},{"key":"S0963548322000086_ref1","first-page":"163","article-title":"On the Hajnal-Szemer\u00e9di theorem on disjoint cliques","volume":"17","author":"Catlin","year":"1980","journal-title":"Util. Math"},{"key":"S0963548322000086_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-014-1410-8"},{"key":"S0963548322000086_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199908)31:4<275::AID-JGT2>3.0.CO;2-F"},{"key":"S0963548322000086_ref2","unstructured":"[2] Ergemlidze, B. and Molla, T. (2021) Transversal Ck-factors in subgraphs of the balanced blow-up of Ck , arXiv:2103.09745."},{"key":"S0963548322000086_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831200048X"},{"key":"S0963548322000086_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00373-9"},{"key":"S0963548322000086_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.04.003"},{"key":"S0963548322000086_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007042"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000086","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,13]],"date-time":"2022-10-13T04:52:30Z","timestamp":1665636750000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000086\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,30]]},"references-count":11,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["S0963548322000086"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000086","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,30]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}