{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T01:09:32Z","timestamp":1762045772030,"version":"build-2065373602"},"reference-count":71,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2022,1,11]],"date-time":"2022-01-11T00:00:00Z","timestamp":1641859200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a fixed graph<jats:italic>H<\/jats:italic>that embeds in a surface<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000560_inline1.png\"\/><jats:tex-math>$\\Sigma$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, what is the maximum number of copies of<jats:italic>H<\/jats:italic>in an<jats:italic>n<\/jats:italic>-vertex graph<jats:italic>G<\/jats:italic>that embeds in<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000560_inline2.png\"\/><jats:tex-math>$\\Sigma$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>? We show that the answer is<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000560_inline3.png\"\/><jats:tex-math>$\\Theta(n^{f(H)})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where<jats:italic>f<\/jats:italic>(<jats:italic>H<\/jats:italic>) is a graph invariant called the \u2018flap-number\u2019 of<jats:italic>H<\/jats:italic>, which is independent of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000560_inline4.png\"\/><jats:tex-math>$\\Sigma$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. This simultaneously answers two open problems posed by Eppstein ((1993)<jats:italic>J. Graph Theory<\/jats:italic><jats:bold>17<\/jats:bold>(3) 409\u2013416.). The same proof also answers the question for minor-closed classes. That is, if<jats:italic>H<\/jats:italic>is a<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000560_inline5.png\"\/><jats:tex-math>$K_{3,t}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>minor-free graph, then the maximum number of copies of<jats:italic>H<\/jats:italic>in an<jats:italic>n<\/jats:italic>-vertex<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000560_inline6.png\"\/><jats:tex-math>$K_{3,t}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>minor-free graph G is<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000560_inline7.png\"\/><jats:tex-math>$\\Theta(n^{f'(H)})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where<jats:italic>f<\/jats:italic>\u2032(<jats:italic>H<\/jats:italic>) is a graph invariant closely related to the flap-number of<jats:italic>H<\/jats:italic>. Finally, when<jats:italic>H<\/jats:italic>is a complete graph we give more precise answers.<\/jats:p>","DOI":"10.1017\/s0963548321000560","type":"journal-article","created":{"date-parts":[[2022,1,11]],"date-time":"2022-01-11T08:44:43Z","timestamp":1641890683000},"page":"812-839","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["Subgraph densities in a surface"],"prefix":"10.1017","volume":"31","author":[{"given":"Tony","family":"Huynh","sequence":"first","affiliation":[]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2022,1,11]]},"reference":[{"key":"S0963548321000560_ref40","doi-asserted-by":"publisher","DOI":"10.4153\/S0008414X21000316"},{"key":"S0963548321000560_ref39","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2010-00687-X"},{"key":"S0963548321000560_ref68","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0738-8"},{"key":"S0963548321000560_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00047-4"},{"key":"S0963548321000560_ref50","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2019.103026"},{"key":"S0963548321000560_ref42","doi-asserted-by":"publisher","DOI":"10.1007\/BF01104169"},{"key":"S0963548321000560_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2010.05.003"},{"key":"S0963548321000560_ref55","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.03.007"},{"key":"S0963548321000560_ref45","unstructured":"[45] Liu, C.-H. (2021) Homomorphism counts in robustly sparse graphs. arXiv:2107.00874."},{"key":"S0963548321000560_ref61","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2016.184.3.1"},{"key":"S0963548321000560_ref63","unstructured":"[63] Sulanke, T. (2006) Generating irreducible triangulations of surfaces. arXiv:0606687."},{"key":"S0963548321000560_ref20","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08715-7"},{"key":"S0963548321000560_ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.01.004"},{"key":"S0963548321000560_ref52","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(87)90028-1"},{"key":"S0963548321000560_ref56","article-title":"A unified approach to structural limits and limits of graphs with bounded tree-depth","volume":"263","author":"Ne\u0161et\u0159il","year":"2020","journal-title":"Mem. Am. Math. Soc."},{"key":"S0963548321000560_ref48","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-5438-2_41"},{"key":"S0963548321000560_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-014-0258-7"},{"key":"S0963548321000560_ref33","doi-asserted-by":"publisher","DOI":"10.37236\/9603"},{"key":"S0963548321000560_ref44","doi-asserted-by":"publisher","DOI":"10.1137\/140979988"},{"key":"S0963548321000560_ref70","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972700010182"},{"key":"S0963548321000560_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/16M109898X"},{"key":"S0963548321000560_ref14","unstructured":"[14] Chan, T. F. N. , Kr\u00e1\u013e, D. , Mohar, B. and Wood, D. R. (2021) Inducibility and universality for trees, arXiv:2102.02010."},{"key":"S0963548321000560_ref31","unstructured":"[31] Gy\u0151ri, E. , Paulos, A. , Salia, N. , Tompkins, C. and Zamora, O. (2019 a) The maximum number of paths of length three in a planar graph. arXiv:1909.13539."},{"key":"S0963548321000560_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2019.103001"},{"key":"S0963548321000560_ref3","first-page":"567","article-title":"Many cliques in H-free subgraphs of random graphs","volume":"9","author":"Alon","year":"2018","journal-title":"J. Comb."},{"key":"S0963548321000560_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.03.004"},{"key":"S0963548321000560_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.04.004"},{"key":"S0963548321000560_ref57","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2010-05189-X"},{"key":"S0963548321000560_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190170314"},{"key":"S0963548321000560_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21865"},{"key":"S0963548321000560_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02767355"},{"key":"S0963548321000560_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.04.001"},{"key":"S0963548321000560_ref64","unstructured":"[64] Sulanke, T. (2006) Irreducible triangulations of low genus surfaces. arXiv:0606690."},{"key":"S0963548321000560_ref65","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.001"},{"key":"S0963548321000560_ref29","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1959.11989408"},{"key":"S0963548321000560_ref67","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":"S0963548321000560_ref34","article-title":"The maximum number of $P_\\ell$ copies in $P_k$ -free graphs","volume":"21","author":"Gy\u0151ri","year":"2019","journal-title":"Discrete Math. Theor. Comput. Sci."},{"first-page":"431","year":"1976","author":"Lov\u00e1sz","key":"S0963548321000560_ref47"},{"key":"S0963548321000560_ref19","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-35.1.85"},{"key":"S0963548321000560_ref46","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/060"},{"key":"S0963548321000560_ref59","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009085"},{"key":"S0963548321000560_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2019.06.022"},{"key":"S0963548321000560_ref54","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190200211"},{"key":"S0963548321000560_ref26","unstructured":"[26] Gerbner, D. , Nagy, Z. L. and Vizer, M. (2020) Unified approach to the generalized Tur\u00e1n problem and supersaturation. arXiv:2008.12093."},{"key":"S0963548321000560_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2003.07.001"},{"key":"S0963548321000560_ref53","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar","year":"2001"},{"key":"S0963548321000560_ref62","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-65759-7"},{"key":"S0963548321000560_ref43","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.9999"},{"key":"S0963548321000560_ref51","first-page":"60","article-title":"Problem 28","volume":"10","author":"Mantel","year":"1907","journal-title":"Wiskundige Opgaven"},{"key":"S0963548321000560_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02764905"},{"key":"S0963548321000560_ref49","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.08.005"},{"key":"S0963548321000560_ref58","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.01.006"},{"key":"S0963548321000560_ref60","doi-asserted-by":"publisher","DOI":"10.1145\/1597036.1597043"},{"key":"S0963548321000560_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22390"},{"key":"S0963548321000560_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760664"},{"key":"S0963548321000560_ref35","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190030108"},{"key":"S0963548321000560_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2018.11.012"},{"key":"S0963548321000560_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20414"},{"key":"S0963548321000560_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190040411"},{"key":"S0963548321000560_ref32","unstructured":"[32] Gy\u0151ri, E. , Paulos, A. , Salia, N. , Tompkins, C. and Zamora, O. (2019 b) The maximum number of pentagons in a planar graph. arXiv:1909.13532."},{"key":"S0963548321000560_ref2","first-page":"25","volume":"87","author":"Alon","year":"1984"},{"key":"S0963548321000560_ref10","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v6-96"},{"key":"S0963548321000560_ref16","doi-asserted-by":"publisher","DOI":"10.37236\/5943"},{"key":"S0963548321000560_ref30","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2013.177.2.10"},{"key":"S0963548321000560_ref66","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-019-02054-x"},{"key":"S0963548321000560_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190100313"},{"key":"S0963548321000560_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112317"},{"key":"S0963548321000560_ref12","unstructured":"[12] Bubeck, S. , Edwards, K. , Mania, H. and Supko, C. (2016) On paths, stars and wyes in trees. arXiv:1601.01950."},{"key":"S0963548321000560_ref71","first-page":"163","article-title":"On some properties of linear complexes","volume":"24","author":"Zykov","year":"1949","journal-title":"Mat. Sbornik N.S."},{"key":"S0963548321000560_ref6","unstructured":"[6] Alweiss, R. , Lovett, S. , Wu, K. and Zhang, J. (to appear) Improved bounds for the sunflower lemma. Ann. Math. arXiv:1908.08483."},{"key":"S0963548321000560_ref69","article-title":"Cliques in graphs excluding a complete graph minor","volume":"23","author":"Wood","year":"2016","journal-title":"Electr. J. Comb."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000560","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T17:11:10Z","timestamp":1700068270000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000560\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,11]]},"references-count":71,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["S0963548321000560"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000560","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2022,1,11]]},"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"}}]}}