{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T12:13:31Z","timestamp":1772453611661,"version":"3.50.1"},"reference-count":44,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2013,1,3]],"date-time":"2013-01-03T00:00:00Z","timestamp":1357171200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p>A graph is called<jats:italic>universal<\/jats:italic>for a given graph class<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char1\"\/><\/jats:private-char>(or, equivalently,<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char1\"\/><\/jats:private-char>-<jats:italic>universal<\/jats:italic>) if it contains a copy of every graph in<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char1\"\/><\/jats:private-char>as a subgraph. The construction of sparse universal graphs for various classes<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char1\"\/><\/jats:private-char>has received a considerable amount of attention. There is particular interest in tight<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char1\"\/><\/jats:private-char>-universal graphs, that is, graphs whose number of vertices is equal to the largest number of vertices in a graph from<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char1\"\/><\/jats:private-char>. Arguably, the most studied case is that when<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char1\"\/><\/jats:private-char>is some class of trees. In this work, we are interested in<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char2\"\/><\/jats:private-char>(<jats:italic>n<\/jats:italic>,\u0394), the class of all<jats:italic>n<\/jats:italic>-vertex trees with maximum degree at most \u0394. We show that every<jats:italic>n<\/jats:italic>-vertex graph satisfying certain natural expansion properties is<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char2\"\/><\/jats:private-char>(<jats:italic>n<\/jats:italic>,\u0394)-universal. Our methods also apply to the case when \u0394 is some function of<jats:italic>n<\/jats:italic>. Since random graphs are known to be good expanders, our result implies, in particular, that there exists a positive constant<jats:italic>c<\/jats:italic>such that the random graph<jats:italic>G(n,cn<\/jats:italic><jats:sup>\u22121\/3<\/jats:sup>log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic>) is asymptotically almost surely (a.a.s.) universal for<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char2\"\/><\/jats:private-char>(<jats:italic>n,O<\/jats:italic>(1)). Moreover, a corresponding result holds for the random regular graph of degree<jats:italic>cn<\/jats:italic><jats:sup>2\/3<\/jats:sup>log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic>. Another interesting consequence is the existence of locally sparse<jats:italic>n<\/jats:italic>-vertex<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char2\"\/><\/jats:private-char>(<jats:italic>n<\/jats:italic>,\u0394)-universal graphs. For example, we show that one can (randomly) construct<jats:italic>n<\/jats:italic>-vertex<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char2\"\/><\/jats:private-char>(<jats:italic>n,O<\/jats:italic>(1))-universal graphs with clique number at most five. This complements the construction of Bhatt, Chung, Leighton and Rosenberg (1989), whose<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char2\"\/><\/jats:private-char>(<jats:italic>n<\/jats:italic>,\u0394)-universal graphs with merely<jats:italic>O(n)<\/jats:italic>edges contain large cliques of size \u03a9(\u0394). Finally, we show that random graphs are robustly<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000533_char2\"\/><\/jats:private-char>(<jats:italic>n<\/jats:italic>,\u0394)-universal in the context of the Maker\u2013Breaker tree-universality game.<\/jats:p>","DOI":"10.1017\/s0963548312000533","type":"journal-article","created":{"date-parts":[[2013,1,3]],"date-time":"2013-01-03T13:41:43Z","timestamp":1357220503000},"page":"253-281","source":"Crossref","is-referenced-by-count":9,"title":["Expanders Are Universal for the Class of All Spanning Trees"],"prefix":"10.1017","volume":"22","author":[{"given":"DANIEL","family":"JOHANNSEN","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MICHAEL","family":"KRIVELEVICH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WOJCIECH","family":"SAMOTIJ","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,1,3]]},"reference":[{"key":"S0963548312000533_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00464-2"},{"key":"S0963548312000533_ref26","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"S0963548312000533_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579202"},{"key":"S0963548312000533_ref19","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-27.2.203"},{"key":"S0963548312000533_ref18","first-page":"136","volume-title":"Proc. 2nd International Conference on Combinatorial Mathematics","author":"Chung","year":"1979"},{"key":"S0963548312000533_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90072-2"},{"key":"S0963548312000533_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301446"},{"key":"S0963548312000533_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20337"},{"key":"S0963548312000533_ref23","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1956.1056816"},{"key":"S0963548312000533_ref36","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070204"},{"key":"S0963548312000533_ref22","doi-asserted-by":"publisher","DOI":"10.1137\/10079882X"},{"key":"S0963548312000533_ref14","unstructured":"B\u00f6ttcher J. , Taraz A. and W\u00fcrfl A. (2011) Private communication."},{"key":"S0963548312000533_ref13","first-page":"35","volume-title":"Graph Theory and Combinatorics","author":"Bollob\u00e1s","year":"1984"},{"key":"S0963548312000533_ref12","doi-asserted-by":"publisher","DOI":"10.1137\/0402014"},{"key":"S0963548312000533_ref33","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548312000533_ref11","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1988-0938689-5"},{"key":"S0963548312000533_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20345"},{"key":"S0963548312000533_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90056-1"},{"key":"S0963548312000533_ref6","first-page":"21","article-title":"On graphs which contain all sparse graphs.","volume":"12","author":"Babai","year":"1982","journal-title":"Ann. Discrete Math."},{"key":"S0963548312000533_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2182-z"},{"key":"S0963548312000533_ref29","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20121"},{"key":"S0963548312000533_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579172"},{"key":"S0963548312000533_ref44","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2422-5"},{"key":"S0963548312000533_ref43","first-page":"225","article-title":"A note on universal graphs.","volume":"11","author":"R\u00f6dl","year":"1981","journal-title":"Ars Combinatoria"},{"key":"S0963548312000533_ref30","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0118(200103)36:3<121::AID-JGT1000>3.0.CO;2-U"},{"key":"S0963548312000533_ref4","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892007"},{"key":"S0963548312000533_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01897304"},{"key":"S0963548312000533_ref21","first-page":"231","volume-title":"LATIN '12: Proc. 10th Latin American International Conference on Theoretical Informatics","author":"Dellamonica","year":"2012"},{"key":"S0963548312000533_ref32","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20472"},{"key":"S0963548312000533_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(01)00455-1"},{"key":"S0963548312000533_ref7","doi-asserted-by":"crossref","first-page":"R6","DOI":"10.37236\/278","article-title":"Large bounded degree trees in expanding graphs","volume":"17","author":"Balogh","year":"2010","journal-title":"Electron. J. Combin."},{"key":"S0963548312000533_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(73)90005-8"},{"key":"S0963548312000533_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20143"},{"key":"S0963548312000533_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2362-0"},{"key":"S0963548312000533_ref34","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004849"},{"key":"S0963548312000533_ref10","volume-title":"Encyclopedia of Mathematics and its Applications","author":"Beck","year":"2008"},{"key":"S0963548312000533_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90021-3"},{"key":"S0963548312000533_ref42","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1307\/mmj\/1029000098","article-title":"On the maximum degree in a random graph.","volume":"15","author":"Moon","year":"1968","journal-title":"Michigan Math. J."},{"key":"S0963548312000533_ref37","doi-asserted-by":"publisher","DOI":"10.1137\/100805753"},{"key":"S0963548312000533_ref38","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10065"},{"key":"S0963548312000533_ref39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32439-3_10"},{"key":"S0963548312000533_ref40","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1013"},{"key":"S0963548312000533_ref41","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90029-E"},{"key":"S0963548312000533_ref20","first-page":"213","volume-title":"Proc. 5th Hungarian Colloquium on Combinatorics","author":"Chung","year":"1978"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000533","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,19]],"date-time":"2020-07-19T18:58:35Z","timestamp":1595185115000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000533\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,3]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["S0963548312000533"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000533","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,3]]}}}