{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:30:51Z","timestamp":1787319051658,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>We prove that asymptotically (as $n\\to\\infty$) almost all graphs with n vertices and $C_dn^{2-\\frac{1}{2d}} \\log^{\\frac{1}{d}} n$ edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs satisfying certain pseudorandom properties. We also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.<\/jats:p>","DOI":"10.1137\/10079882x","type":"journal-article","created":{"date-parts":[[2012,3,15]],"date-time":"2012-03-15T10:13:41Z","timestamp":1331806421000},"page":"353-374","source":"Crossref","is-referenced-by-count":8,"title":["Universality of Random Graphs"],"prefix":"10.1137","volume":"26","author":[{"suffix":"Jr.","given":"Domingos","family":"Dellamonica,","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yoshiharu","family":"Kohayakawa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vojt\u011bch","family":"R\u00f6dl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Ruci\u0144ski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,3,13]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Alon, M. Capalbo, Y. Kohayakawa, V. R\u00f6dl, A. Ruci\u0144ski, and E. Szemer\u00e9di,\n                      Universality and tolerance (extended abstract)\n                      , in Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE, Los Alamitos, CA, 2000, pp. 14\u201321.","DOI":"10.1109\/SFCS.2000.892007"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Alon, M. Capalbo, Y. Kohayakawa, V. R\u00f6dl, A. Ruci\u0144ski, and E. Szemer\u00e9di,\n                      Near-optimum universal graphs for graphs with bounded degrees (extended abstract)\n                      , in Approximation, Randomization, and Combinatorial Optimization (Berkeley, CA, 2001), Lecture Notes in Comput. Sci. 2129, Springer, Berlin, 2001, pp. 170\u2013180.","DOI":"10.1007\/3-540-44666-4_20"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20143"},{"key":"R4","unstructured":"N. Alon and M. Capalbo,\n                      Optimal universal graphs with deterministic embedding\n                      , in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2008, pp. 373\u2013378."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271712"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2182-z"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"J. Balogh, B. Csaba, M. Pei, and W. Samotij,\n                      Large bounded degree trees in expanding graphs\n                      , Electron. J. Combin., 17 (2010).","DOI":"10.37236\/278"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0402014"},{"key":"R9","unstructured":"B. Bollob\u00e1s,\n                      Random Graphs\n                      , Cambridge Stud. Adv. Math. 73, 2nd ed., Cambridge University Press, Cambridge, UK, 2001."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"M. R. Capalbo and S. R. Kosaraju,\n                      Small universal graphs\n                      , in Proceedings of the Annual ACM Symposium on Theory of Computing, ACM, New York, 1999, pp. 741\u2013749.","DOI":"10.1145\/301250.301446"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"D. Dellamonica, Jr., and Y. Kohayakawa,\n                      An algorithmic Friedman-Pippenger theorem on tree embeddings and applications\n                      , Electron. J. Combin., 15 (2008).","DOI":"10.37236\/851"},{"key":"R12","first-page":"455","volume":"8","author":"Erd\u0151s P.","year":"1964","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20121"},{"key":"R14","unstructured":"A. Hajnal and E. Szemer\u00e9di,\n                      Proof of a conjecture of P. Erd\u0151s\n                      , in Combinatorial Theory and Its Applications, II, North-Holland, Amsterdam, 1970, pp. 601\u2013623."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Rucinski,\n                      Random Graphs\n                      , Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20224"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.0.CO;2-Q"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399004150"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399003879"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050063"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/10079882X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:44:44Z","timestamp":1787316284000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/10079882X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/10079882X"],"URL":"https:\/\/doi.org\/10.1137\/10079882x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}