{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T21:05:41Z","timestamp":1775163941990,"version":"3.50.1"},"reference-count":47,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2023,9,5]],"date-time":"2023-09-05T00:00:00Z","timestamp":1693872000000},"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":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study generalised quasirandom graphs whose vertex set consists of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000263_inline1.png\"\/><jats:tex-math>$q$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>parts (of not necessarily the same sizes) with edges within each part and between each pair of parts distributed quasirandomly; such graphs correspond to the stochastic block model studied in statistics and network science. Lov\u00e1sz and S\u00f3s showed that the structure of such graphs is forced by homomorphism densities of graphs with at most<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000263_inline2.png\"\/><jats:tex-math>$(10q)^q+q$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>vertices; subsequently, Lov\u00e1sz refined the argument to show that graphs with<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000263_inline3.png\"\/><jats:tex-math>$4(2q+3)^8$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>vertices suffice. Our results imply that the structure of generalised quasirandom graphs with<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000263_inline4.png\"\/><jats:tex-math>$q\\ge 2$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>parts is forced by homomorphism densities of graphs with at most<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000263_inline5.png\"\/><jats:tex-math>$4q^2-q$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>vertices, and, if vertices in distinct parts have distinct degrees, then<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000263_inline6.png\"\/><jats:tex-math>$2q+1$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>vertices suffice. The latter improves the bound of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000263_inline7.png\"\/><jats:tex-math>$8q-4$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>due to Spencer.<\/jats:p>","DOI":"10.1017\/s0963548323000263","type":"journal-article","created":{"date-parts":[[2023,9,5]],"date-time":"2023-09-05T08:42:46Z","timestamp":1693903366000},"page":"16-31","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Forcing generalised quasirandom graphs efficiently"],"prefix":"10.1017","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2770-7180","authenticated-orcid":false,"given":"Andrzej","family":"Grzesik","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8680-0890","authenticated-orcid":false,"given":"Daniel","family":"Kr\u00e1l\u2019","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9657-4011","authenticated-orcid":false,"given":"Oleg","family":"Pikhurko","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,9,5]]},"reference":[{"key":"S0963548323000263_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(92)90053-W"},{"key":"S0963548323000263_ref46","first-page":"307","article-title":"Pseudo-random graphs","volume":"144","author":"Thomason","year":"1987","journal-title":"Ann. Discrete Math."},{"key":"S0963548323000263_ref22","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007236"},{"key":"S0963548323000263_ref36","volume-title":"Large Networks and Graph Limits","volume":"60","author":"Lov\u00e1sz","year":"2012"},{"key":"S0963548323000263_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2018.10.019"},{"key":"S0963548323000263_ref18","first-page":"165","volume-title":"Graph Theory and Related Topics","author":"Erd\u0151s","year":"1979"},{"key":"S0963548323000263_ref47","first-page":"173","volume-title":"Surveys in Combinatorics","volume":"123","author":"Thomason","year":"1987"},{"key":"S0963548323000263_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90093-9"},{"key":"S0963548323000263_ref13","doi-asserted-by":"publisher","DOI":"10.37236\/6557"},{"key":"S0963548323000263_ref6","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1991-1077279-1"},{"key":"S0963548323000263_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-018-0878-1"},{"key":"S0963548323000263_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-013-0216-9"},{"key":"S0963548323000263_ref30","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1454"},{"key":"S0963548323000263_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-020-4371-y"},{"key":"S0963548323000263_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22044"},{"key":"S0963548323000263_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125347"},{"key":"S0963548323000263_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.01.006"},{"key":"S0963548323000263_ref41","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20117"},{"key":"S0963548323000263_ref16","first-page":"33","article-title":"Graph limits and exchangeable random graphs","volume":"28","author":"Diaconis","year":"2008","journal-title":"Rend. Mat. Appl."},{"key":"S0963548323000263_ref17","unstructured":"[17] Eberhard, S. , Manners, F. and Mrazovi\u0107, R. (2022) Transversals in quasirandom Latin squares, preprint arXiv: 2209.02180."},{"key":"S0963548323000263_ref19","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1354"},{"key":"S0963548323000263_ref40","doi-asserted-by":"crossref","unstructured":"[40] Macdonald, I. G. (1995) Symmetric Functions and Hall Polynomials, 2nd edition. Oxford University Press.","DOI":"10.1093\/oso\/9780198534891.001.0001"},{"key":"S0963548323000263_ref23","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2007.166.897"},{"key":"S0963548323000263_ref45","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14444-8_18"},{"key":"S0963548323000263_ref2","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOS1985"},{"key":"S0963548323000263_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21060"},{"key":"S0963548323000263_ref38","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.002"},{"key":"S0963548323000263_ref42","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(86)90076-2"},{"key":"S0963548323000263_ref43","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20017"},{"key":"S0963548323000263_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190150206"},{"key":"S0963548323000263_ref20","unstructured":"[20] Garbe, F. , Hancock, R. , Hladk\u00fd, J. and Sharifzadeh, M. (2020) Limits of Latin squares, preprint arXiv: 2010.07854."},{"key":"S0963548323000263_ref32","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2001.3217"},{"key":"S0963548323000263_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.06.005"},{"key":"S0963548323000263_ref35","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548321000298"},{"key":"S0963548323000263_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008826"},{"key":"S0963548323000263_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0044-0"},{"key":"S0963548323000263_ref44","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020102"},{"key":"S0963548323000263_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20956"},{"key":"S0963548323000263_ref15","unstructured":"[15] Coregliano, L. N. and Razborov, A. A. (2020) Natural quasirandomness properties, preprint arXiv: 2012.11773."},{"key":"S0963548323000263_ref33","article-title":"Finitely forcible graphons with an almost arbitrary structure","volume":"2020","author":"Kr\u00e1l\u2019","year":"2020","journal-title":"Discrete Anal."},{"key":"S0963548323000263_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2022.103632"},{"key":"S0963548323000263_ref27","doi-asserted-by":"publisher","DOI":"10.1112\/plms.12382"},{"key":"S0963548323000263_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.07.007"},{"key":"S0963548323000263_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010108"},{"key":"S0963548323000263_ref26","unstructured":"[26] Grzesik, A. , Il\u2019kovi\u010d, D. , Kielak, B. and Kr\u00e1l\u2019, D. (2022) Quasirandom forcing orientations of cycles, preprint arXiv: 2212.09343."},{"key":"S0963548323000263_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.03.005"},{"key":"S0963548323000263_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-020-00553-1"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548323000263","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T01:26:22Z","timestamp":1703121982000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548323000263\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,5]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["S0963548323000263"],"URL":"https:\/\/doi.org\/10.1017\/s0963548323000263","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,5]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. 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"}]}}