{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T04:59:46Z","timestamp":1784005186443,"version":"3.55.0"},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T00:00:00Z","timestamp":1655078400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"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>In 1975 Bollob\u00e1s, Erd\u0151s, and Szemer\u00e9di asked the following question: given positive integers <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline1.png\"\/><jats:tex-math>\n$n, t, r$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline2.png\"\/><jats:tex-math>\n$2\\le t\\le r-1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, what is the largest minimum degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline3.png\"\/><jats:tex-math>\n$\\delta (G)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> among all <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline4.png\"\/><jats:tex-math>\n$r$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-partite graphs <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline5.png\"\/><jats:tex-math>\n$G$\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=\"S0963548322000141_inline6.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and which do not contain a copy of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline7.png\"\/><jats:tex-math>\n$K_{t+1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>? The <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline8.png\"\/><jats:tex-math>\n$r=t+1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> case has attracted a lot of attention and was fully resolved by Haxell and Szab\u00f3, and Szab\u00f3 and Tardos in 2006. In this article, we investigate the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline9.png\"\/><jats:tex-math>\n$r\\gt t+1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> case of the problem, which has remained dormant for over 40 years. We resolve the problem exactly in the case when <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline10.png\"\/><jats:tex-math>\n$r \\equiv -1 \\pmod{t}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, and up to an additive constant for many other cases, including when <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline11.png\"\/><jats:tex-math>\n$r \\geq (3t-1)(t-1)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Our approach utilizes a connection to the related problem of determining the maximum of the minimum degrees among the family of balanced <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline12.png\"\/><jats:tex-math>\n$r$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-partite <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline13.png\"\/><jats:tex-math>\n$rn$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex graphs of chromatic number at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000141_inline14.png\"\/><jats:tex-math>\n$t$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548322000141","type":"journal-article","created":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T19:43:37Z","timestamp":1655149417000},"page":"1092-1101","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":4,"title":["Complete subgraphs in a multipartite graph"],"prefix":"10.1017","volume":"31","author":[{"given":"Allan","family":"Lo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Treglown","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yi","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2022,6,13]]},"reference":[{"key":"S0963548322000141_ref8","doi-asserted-by":"publisher","DOI":"10.37236\/10148"},{"key":"S0963548322000141_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02783300"},{"key":"S0963548322000141_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90133-2"},{"key":"S0963548322000141_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000274"},{"key":"S0963548322000141_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90011-4"},{"key":"S0963548322000141_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0009-y"},{"key":"S0963548322000141_ref7","first-page":"351","volume-title":". In Proceedings of the Conference on Combinatorial Mathematics held at the Mathematical Institute, 3-7 July 1972","author":"Erd\u0151s","year":"1972"},{"key":"S0963548322000141_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2425-5"},{"key":"S0963548322000141_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0019-9"},{"key":"S0963548322000141_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007157"},{"key":"S0963548322000141_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2019.04.007"},{"key":"S0963548322000141_ref4","first-page":"343","article-title":"Complete subgraphs of chromatic graphs and hypergraphs","volume":"6","author":"Bollob\u00e1s","year":"1974","journal-title":"Utilitas Math."},{"key":"S0963548322000141_ref14","first-page":"436","article-title":"On an extremal problem in graph theory","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Mat. Fiz. Lapok"},{"key":"S0963548322000141_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004758"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,13]],"date-time":"2022-10-13T04:52:36Z","timestamp":1665636756000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000141\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,13]]},"references-count":14,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["S0963548322000141"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000141","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,13]]},"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"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}