{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,24]],"date-time":"2023-08-24T09:35:35Z","timestamp":1692869735059},"reference-count":34,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2022,12,9]],"date-time":"2022-12-09T00:00:00Z","timestamp":1670544000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An old conjecture of Erd\u0151s and McKay states that if all homogeneous sets in an <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000347_inline1.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex graph are of order <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000347_inline2.png\" \/><jats:tex-math>\n$O(\\!\\log n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> then the graph contains induced subgraphs of each size from <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000347_inline3.png\" \/><jats:tex-math>\n$\\{0,1,\\ldots, \\Omega \\big(n^2\\big)\\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000347_inline4.png\" \/><jats:tex-math>\n$n \\times n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> bipartite graph are of order <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000347_inline5.png\" \/><jats:tex-math>\n$O(\\!\\log n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then the graph contains induced subgraphs of each size from <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000347_inline6.png\" \/><jats:tex-math>\n$\\{0,1,\\ldots, \\Omega \\big(n^2\\big)\\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548322000347","type":"journal-article","created":{"date-parts":[[2022,12,9]],"date-time":"2022-12-09T11:05:57Z","timestamp":1670583957000},"page":"465-477","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["A bipartite version of the Erd\u0151s\u2013McKay conjecture"],"prefix":"10.1017","volume":"32","author":[{"given":"Eoin","family":"Long","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lauren\u0163iu","family":"Ploscaru","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,12,9]]},"reference":[{"key":"S0963548322000347_ref24","unstructured":"[24] Long, E. and Ploscaru, L. (2022) Distinct degrees and homogeneous sets. arXiv preprint arXiv: 2204.05932, p. 36, https:\/\/arxiv.org\/abs\/2204.05932."},{"key":"S0963548322000347_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10117"},{"key":"S0963548322000347_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018669"},{"key":"S0963548322000347_ref7","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2012.176.3.3"},{"key":"S0963548322000347_ref2","doi-asserted-by":"crossref","unstructured":"[2] Alon, N. and Bollob\u00e1s, B. (1989) Graphs with a small number of distinct induced subgraphs, Discr. Math. 75 23\u201330, ISSN: 0012-365x, https:\/\/www.sciencedirect.com\/science\/article\/pii\/0012365X89900745","DOI":"10.1016\/0012-365X(89)90074-5"},{"key":"S0963548322000347_ref14","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"key":"S0963548322000347_ref15","first-page":"49","volume-title":"Classic Papers in Combinatorics","author":"Erd\u0151s","year":"1987"},{"key":"S0963548322000347_ref23","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rny064"},{"key":"S0963548322000347_ref26","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000256"},{"key":"S0963548322000347_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000146"},{"key":"S0963548322000347_ref31","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2845"},{"key":"S0963548322000347_ref6","unstructured":"[6] Baksys, M. and Chen, X. (2021) On number of different sized induced subgraphs of bipartite-ramsey graphs, arXiv preprint arXiv: 2109.08485, https:\/\/arxiv.org\/abs\/2109.08485"},{"key":"S0963548322000347_ref30","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264"},{"key":"S0963548322000347_ref18","unstructured":"[18] Ferber, A. , Hardiman, L. and Krivelevich, M. (2021) On subgraphs with degrees of prescribed residues in the random graph. arXiv preprint arXiv: 2107.06977."},{"key":"S0963548322000347_ref33","doi-asserted-by":"publisher","DOI":"10.1112\/S0024611504015059"},{"key":"S0963548322000347_ref12","unstructured":"[12] Collins, A. , Riasanovsky, A. , Wallace, J. and Radziszowski, S. (2016) Zarankiewicz numbers and bipartite ramsey numbers, arXiv preprint arXiv: 1604.01257."},{"key":"S0963548322000347_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20317"},{"key":"S0963548322000347_ref21","unstructured":"[21] Kwan, M. , Sah, A. , Sauermann, L. and Sawhney, M. (2022) Anticoncentration in ramsey graphs and a proof of the erd\u0151s\u2013mckay conjecture. arXiv preprint arXiv: 2208.02874."},{"key":"S0963548322000347_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3322-0"},{"key":"S0963548322000347_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-017-3755-0"},{"key":"S0963548322000347_ref29","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1999.2972"},{"key":"S0963548322000347_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511810633"},{"key":"S0963548322000347_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22639"},{"key":"S0963548322000347_ref17","first-page":"231","article-title":"Some of my favourite problems in various branches of combinatorics","volume":"47","author":"Erd\u0151s","year":"1992","journal-title":"Le Matematiche"},{"key":"S0963548322000347_ref3","unstructured":"[3] Alon, N. and Spencer, J. H. (2004) The Probabilistic Method. Second edition. Wiley, ISBN: 0471370460."},{"key":"S0963548322000347_ref32","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103238"},{"key":"S0963548322000347_ref22","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/7729"},{"key":"S0963548322000347_ref11","doi-asserted-by":"publisher","DOI":"10.1201\/9781439863879"},{"key":"S0963548322000347_ref19","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/15060"},{"key":"S0963548322000347_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22463"},{"key":"S0963548322000347_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/20M1321760"},{"key":"S0963548322000347_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.09.006"},{"key":"S0963548322000347_ref20","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"S0963548322000347_ref34","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511755149"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000347","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,12]],"date-time":"2023-04-12T07:27:48Z","timestamp":1681284468000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000347\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,9]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["S0963548322000347"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000347","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,9]]},"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-NonCommercial-ShareAlike licence (https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the same Creative Commons licence is included and the original work is properly cited. The written permission of Cambridge University Press must be obtained for commercial re-use.","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"}]}}