{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T16:33:23Z","timestamp":1777307603381,"version":"3.51.4"},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:00:00Z","timestamp":1605744000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Considering a natural generalization of the Ruzsa\u2013Szemer\u00e9di problem, we prove that for any fixed positive integers <jats:italic>r<\/jats:italic>, <jats:italic>s<\/jats:italic> with <jats:italic>r<\/jats:italic> &lt; <jats:italic>s<\/jats:italic>, there are graphs on <jats:italic>n<\/jats:italic> vertices containing <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000589_inline1.png\"\/><jats:tex-math>\n$n^{r}e^{-O\\left(\\sqrt{\\log{n}}\\right)}=n^{r-o(1)}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> copies of <jats:italic>K<\/jats:italic><jats:sub><jats:italic>s<\/jats:italic><\/jats:sub> such that any <jats:italic>K<\/jats:italic><jats:sub><jats:italic>r<\/jats:italic><\/jats:sub> is contained in at most one <jats:italic>K<\/jats:italic><jats:sub><jats:italic>s<\/jats:italic><\/jats:sub>. We also give bounds for the generalized rainbow Tur\u00e1n problem ex (<jats:italic>n<\/jats:italic>, <jats:italic>H<\/jats:italic>, rainbow - <jats:italic>F<\/jats:italic>) when <jats:italic>F<\/jats:italic> is complete. In particular, we answer a question of Gerbner, M\u00e9sz\u00e1ros, Methuku and Palmer, showing that there are properly edge-coloured graphs on <jats:italic>n<\/jats:italic> vertices with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000589_inline2.png\"\/><jats:tex-math>\n$n^{r-1-o(1)}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> copies of <jats:italic>K<\/jats:italic><jats:sub><jats:italic>r<\/jats:italic><\/jats:sub> such that no <jats:italic>K<\/jats:italic><jats:sub><jats:italic>r<\/jats:italic><\/jats:sub> is rainbow.<\/jats:p>","DOI":"10.1017\/s0963548320000589","type":"journal-article","created":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T07:36:55Z","timestamp":1605771415000},"page":"591-608","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":10,"title":["Generalizations of the Ruzsa\u2013Szemer\u00e9di and rainbow Tur\u00e1n problems for cliques"],"prefix":"10.1017","volume":"30","author":[{"given":"W. T.","family":"Gowers","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barnab\u00e1s","family":"Janzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,11,19]]},"reference":[{"key":"S0963548320000589_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0035-9"},{"key":"S0963548320000589_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007759"},{"key":"S0963548320000589_ref12","unstructured":"[12] Ruzsa, I. Z. and Szemer\u00e9di, E. (1979) Triple systems with no six points carrying three triangles. In Combinatorics (Keszthely, 1976), Vol. 18 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp. 939\u2013945. Akad\u00e9miai Kaid\u00f3."},{"key":"S0963548320000589_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.01.003"},{"key":"S0963548320000589_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.03.004"},{"key":"S0963548320000589_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214074"},{"key":"S0963548320000589_ref6","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"S0963548320000589_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007760"},{"key":"S0963548320000589_ref1","unstructured":"[1] Alon, N. , Lefmann, H. and R\u00f6dl, V. (1992) On an anti-Ramsey type result. In Sets, Graphs and Numbers (Budapest, 1991), Vol. 60 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp. 9\u201322. North-Holland."},{"key":"S0963548320000589_ref10","doi-asserted-by":"crossref","unstructured":"[10] Johnston, D. , Palmer, C. and Sarkar, A. (2016) Rainbow Tur\u00e1n problems for paths and forests of stars. Electron. J. Combin. 24 P1.34.","DOI":"10.37236\/6430"},{"key":"S0963548320000589_ref13","doi-asserted-by":"crossref","unstructured":"[13] S\u00f3s, V. , Erd\u0151s, P. and Brown, W. (1973) On the existence of triangulated spheres in 3-graphs, and related problems. Periodica Math. Hungar. 3 221\u2013228.","DOI":"10.1007\/BF02018585"},{"key":"S0963548320000589_ref8","doi-asserted-by":"publisher","DOI":"10.37236\/7889"},{"key":"S0963548320000589_ref9","unstructured":"[9] Gerbner, D. , M\u00e9sz\u00e1ros, T. , Methuku, A. and Palmer, C. (2019) Generalized rainbow Tur\u00e1n problems. arXiv:1911.06642"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000589","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T14:34:41Z","timestamp":1623335681000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000589\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,19]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["S0963548320000589"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000589","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,19]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. 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 (http:\/\/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"}]}}