{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T03:29:23Z","timestamp":1772249363872,"version":"3.50.1"},"reference-count":39,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"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,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000142_inline1.png\"\/><jats:tex-math>\n$F$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, we consider the problem of determining the densest possible pseudorandom graph that contains no copy of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000142_inline2.png\"\/><jats:tex-math>\n$F$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We provide an embedding procedure that improves a general result of Conlon, Fox, and Zhao which gives an upper bound on the density. In particular, our result implies that optimally pseudorandom graphs with density greater than <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000142_inline3.png\"\/><jats:tex-math>\n$n^{-1\/3}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> must contain a copy of the Peterson graph, while the previous best result gives the bound <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000142_inline4.png\"\/><jats:tex-math>\n$n^{-1\/4}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Moreover, we conjecture that the exponent <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000142_inline5.png\"\/><jats:tex-math>\n$1\/3$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in our bound is tight. We also construct the densest known pseudorandom <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000142_inline6.png\"\/><jats:tex-math>\n$K_{2,3}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-free graphs that are also triangle-free. Finally, we give a different proof for the densest known construction of clique-free pseudorandom graphs due to Bishnoi, Ihringer, and Pepe that they have no large clique.<\/jats:p>","DOI":"10.1017\/s0963548324000142","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T09:38:39Z","timestamp":1714383519000},"page":"583-596","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Tur\u00e1n problems in pseudorandom graphs"],"prefix":"10.1017","volume":"33","author":[{"given":"Xizhi","family":"Liu","sequence":"first","affiliation":[]},{"given":"Dhruv","family":"Mubayi","sequence":"additional","affiliation":[]},{"given":"David","family":"Munh\u00e1 Correia","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"S0963548324000142_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2009.06.008"},{"key":"S0963548324000142_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0029-7"},{"key":"S0963548324000142_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010407"},{"key":"S0963548324000142_ref37","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21890"},{"key":"S0963548324000142_ref26","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"S0963548324000142_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)90107-3"},{"key":"S0963548324000142_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2013.12.004"},{"key":"S0963548324000142_ref35","volume-title":"Calculus on manifolds. A modern approach to classical theorems of advanced calculus","author":"Spivak","year":"1965"},{"key":"S0963548324000142_ref39","first-page":"173","volume-title":"Surveys in Combinatorics 1987 (New Cross 1987)","author":"Thomason","year":"1987"},{"key":"S0963548324000142_ref31","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2024.199.2.8"},{"key":"S0963548324000142_ref22","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-07-04265-1"},{"key":"S0963548324000142_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF03352998"},{"key":"S0963548324000142_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581168"},{"key":"S0963548324000142_ref34","first-page":"623","article-title":"The teaching of mathematics: On \n\n\n\n$(a \\times b) \\times c$","volume":"96","author":"Shaw","year":"1989","journal-title":"Am. Math. Mon."},{"key":"S0963548324000142_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-020-4226-6"},{"key":"S0963548324000142_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548324000142_ref19","unstructured":"19. Erd\u0151s, P. (1975) Some recent progress on extremal problems in graph theory. In Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congressus Numerantium, No. XIV , Utilitas Mathematica, Winnipeg, Manitoba, pp. 3\u201314."},{"key":"S0963548324000142_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2022.112871"},{"key":"S0963548324000142_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90079-0"},{"key":"S0963548324000142_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018821"},{"key":"S0963548324000142_ref16","article-title":"Which graphs can be counted in \n\n\n\n$C_4$\n\n\n-free graphs?","author":"Conlon","journal-title":"Pure Appl. Math. Q."},{"key":"S0963548324000142_ref23","first-page":"228","article-title":"On a problem of Tur\u00e1n in the theory of graphs","volume":"15","author":"Katona","year":"1964","journal-title":"Mat. Lapok"},{"key":"S0963548324000142_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02564418"},{"key":"S0963548324000142_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01836217"},{"key":"S0963548324000142_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32439-3_10"},{"key":"S0963548324000142_ref36","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00482-9"},{"key":"S0963548324000142_ref38","first-page":"307","volume-title":"Random Graphs","author":"Thomason","year":"1987"},{"key":"S0963548324000142_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32439-3_3"},{"key":"S0963548324000142_ref18","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1994.11997042"},{"key":"S0963548324000142_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2006.08.004"},{"key":"S0963548324000142_ref20","first-page":"623","article-title":"On a problem in the theory of graphs","volume":"7","author":"Erd\u0151s","year":"1963, 1962","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"S0963548324000142_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.01.007"},{"key":"S0963548324000142_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2978-6"},{"key":"S0963548324000142_ref5","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1906"},{"key":"S0963548324000142_ref32","doi-asserted-by":"publisher","DOI":"10.4171\/jems\/1359"},{"key":"S0963548324000142_ref15","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1966-036-2"},{"key":"S0963548324000142_ref2","doi-asserted-by":"publisher","DOI":"10.37236\/1192"},{"key":"S0963548324000142_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261323"},{"key":"S0963548324000142_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90052-5"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000142","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T22:46:15Z","timestamp":1728427575000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000142\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["S0963548324000142"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000142","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. 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"}]}}