{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T13:27:03Z","timestamp":1773322023660,"version":"3.50.1"},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T00:00:00Z","timestamp":1618444800000},"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,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Tur\u00e1n number <jats:italic>ex<\/jats:italic>(<jats:italic>n<\/jats:italic>, <jats:italic>H<\/jats:italic>) of a graph <jats:italic>H<\/jats:italic> is the maximal number of edges in an <jats:italic>H<\/jats:italic>-free graph on <jats:italic>n<\/jats:italic> vertices. In 1983, Chung and Erd\u0151s asked which graphs <jats:italic>H<\/jats:italic> with <jats:italic>e<\/jats:italic> edges minimise <jats:italic>ex<\/jats:italic>(<jats:italic>n<\/jats:italic>, <jats:italic>H<\/jats:italic>). They resolved this question asymptotically for most of the range of <jats:italic>e<\/jats:italic> and asked to complete the picture. In this paper, we answer their question by resolving all remaining cases. Our result translates directly to the setting of universality, a well-studied notion of finding graphs which contain every graph belonging to a certain family. In this setting, we extend previous work done by Babai, Chung, Erd\u0151s, Graham and Spencer, and by Alon and Asodi.<\/jats:p>","DOI":"10.1017\/s0963548321000110","type":"journal-article","created":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T07:46:38Z","timestamp":1618472798000},"page":"942-955","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":4,"title":["Universal and unavoidable graphs"],"prefix":"10.1017","volume":"30","author":[{"given":"Matija","family":"Buci\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nemanja","family":"Dragani\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Sudakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,4,15]]},"reference":[{"key":"S0963548321000110_ref5","doi-asserted-by":"crossref","unstructured":"[5] Babai, L. , Chung, F. R. K. , Erd\u0151s, P. , Graham, R. L. and Spencer, J. H. (1982) On graphs which contain all sparse graphs. In Theory and Practice of Combinatorics, Vol. 60 of North-Holland Mathematics Studies, pp. 21\u201326.","DOI":"10.1016\/S0304-0208(08)73486-8"},{"key":"S0963548321000110_ref13","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1111\/j.1749-6632.1979.tb32784.x","article-title":"On universal graphs","volume":"319","author":"Chung","year":"1979","journal-title":"Ann. New York Acad. Sci."},{"key":"S0963548321000110_ref24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.aim.2019.106793","article-title":"Spanning trees in random graphs","volume":"356","author":"Montgomery","year":"2019","journal-title":"Adv. Math."},{"key":"S0963548321000110_ref3","unstructured":"[3] Alon, N. and Capalbo, M. (2008) Optimal universal graphs with deterministic embedding. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, pp. 373\u2013378."},{"key":"S0963548321000110_ref11","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1002\/jgt.3190110215","article-title":"On unavoidable hypergraphs","volume":"11","author":"Chung","year":"1987","journal-title":"J. Graph Theory"},{"key":"S0963548321000110_ref12","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF02579173","article-title":"Minimal decompositions of graphs into mutually isomorphic subgraphs","volume":"1","author":"Chung","year":"1981","journal-title":"Combinatorica"},{"key":"S0963548321000110_ref10","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF02579290","article-title":"On unavoidable graphs","volume":"3","author":"Chung","year":"1983","journal-title":"Combinatorica"},{"key":"S0963548321000110_ref8","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1016\/0097-3165(83)90011-0","article-title":"Unavoidable stars in 3-graphs","volume":"35","author":"Chung","year":"1983","journal-title":"J. Combin. Theory Ser. A"},{"key":"S0963548321000110_ref21","doi-asserted-by":"crossref","unstructured":"[21] F\u00fcredi, Z. and Simonovits, M. (2013) The history of degenerate (bipartite) extremal graph problems. In Erd\u0151s Centennial, Vol. 25 of Bolyai Society Mathematical Studies, J\u00e1nos Bolyai Mathematical Society, Budapest, pp. 169\u2013264.","DOI":"10.1007\/978-3-642-39286-3_7"},{"key":"S0963548321000110_ref17","unstructured":"[17] Duke, R. A. and Erd\u0151s, P. (1977) Systems of finite sets having a common intersection. In Proceedings. 8th SE Conference on Combinatorics, Graph Theory and Computing, pp. 247\u2013252."},{"key":"S0963548321000110_ref6","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1137\/0402014","article-title":"Universal graphs for bounded-degree trees and planar graphs","volume":"2","author":"Bhatt","year":"1989","journal-title":"SIAM J. Discrete Math."},{"key":"S0963548321000110_ref18","first-page":"51","article-title":"A limit theorem in graph theory","volume":"1","author":"Erd\u0151s","year":"1966","journal-title":"Studia Sci. Math. Hungar."},{"key":"S0963548321000110_ref22","doi-asserted-by":"crossref","DOI":"10.37236\/5562","article-title":"On universal hypergraphs","volume":"23","author":"Hetterich","year":"2016","journal-title":"Electron. J. Combin."},{"key":"S0963548321000110_ref2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/rsa.20143","article-title":"Sparse universal graphs for bounded-degree graphs","volume":"31","author":"Alon","year":"2007","journal-title":"Random Struct. Algorithms"},{"key":"S0963548321000110_ref14","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1112\/jlms\/s2-27.2.203","article-title":"On universal graphs for spanning trees","volume":"27","author":"Chung","year":"1983","journal-title":"J. London Math. Soc. (2)"},{"key":"S0963548321000110_ref23","doi-asserted-by":"crossref","unstructured":"[23] Keevash, P. (2011) Hypergraph Tur\u00e1n problems. In Surveys in Combinatorics 2011, London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, pp. 83\u2013139.","DOI":"10.1017\/CBO9781139004114.004"},{"key":"S0963548321000110_ref16","doi-asserted-by":"crossref","unstructured":"[16] Conlon, D. , Ferber, A. , Nenadov, R. and \u0160kori\u0107, N. (2017) Almost-spanning universality in random graphs. Random Struct. Algorithms 50(3) 380\u2013393.","DOI":"10.1002\/rsa.20661"},{"key":"S0963548321000110_ref1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0377-0427(01)00455-1","article-title":"Sparse universal graphs","volume":"142","author":"Alon","year":"2002","journal-title":"J. Comput. Appl. Math."},{"key":"S0963548321000110_ref19","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1090\/S0002-9904-1946-08715-7","article-title":"On the structure of linear graphs","volume":"52","author":"Erd\u0151s","year":"1946","journal-title":"Bull. Amer. Math. Soc."},{"key":"S0963548321000110_ref25","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF01929486","article-title":"What we know and what we do not know about Tur\u00e1n numbers","volume":"11","author":"Sidorenko","year":"1995","journal-title":"Graphs Comb."},{"key":"S0963548321000110_ref15","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1112\/jlms\/s2-23.2.207","article-title":"On the Erd\u0151s-Stone theorem","volume":"2","author":"Chv\u00e1tal","year":"1981","journal-title":"J. London Math. Soc. (2)"},{"key":"S0963548321000110_ref26","unstructured":"[26] Sudakov, B. (2010) Recent developments in extremal combinatorics: Ramsey and Tur\u00e1n type problems. In Proceedings of the International Congress of Mathematicians, Volume IV, Hindustan Book Agency, New Delhi, pp. 2579\u20132606."},{"key":"S0963548321000110_ref20","doi-asserted-by":"crossref","unstructured":"[20] F\u00fcredi, Z. (1991) Tur\u00e1n type problems. In Surveys in Combinatorics, (Guildford, 1991), Vol. 166, London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, pp. 253\u2013300.","DOI":"10.1017\/CBO9780511666216.010"},{"key":"S0963548321000110_ref4","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1007\/s00493-007-2182-z","article-title":"Embedding nearly-spanning bounded degree trees","volume":"27","author":"Alon","year":"2007","journal-title":"Combinatorica"},{"key":"S0963548321000110_ref27","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":"S0963548321000110_ref9","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1002\/(SICI)1097-0118(199705)25:1<3::AID-JGT1>3.0.CO;2-R","article-title":"Open problems of Paul Erd\u0151s in graph theory","volume":"25","author":"Chung","year":"1997","journal-title":"J. Graph Theory"},{"key":"S0963548321000110_ref7","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1112\/blms\/5.3.317","article-title":"On the structure of edge graphs","volume":"5","author":"Bollob\u00e1s","year":"1973","journal-title":"Bull. London Math. Soc."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T15:50:47Z","timestamp":1634313047000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000110\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,15]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["S0963548321000110"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000110","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,15]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. 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"}]}}