{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T15:51:04Z","timestamp":1717257064733},"reference-count":21,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2014,5,22]],"date-time":"2014-05-22T00:00:00Z","timestamp":1400716800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 1301698"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 1102086"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS 0800070"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"S\u00e3o Paulo Research Foundation","doi-asserted-by":"publisher","award":["2013\/03447-6, 2013\/07699-0"],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Polish NSC grant","award":["N201 604940"]},{"name":"CAPES-Fulbright","award":["Scholarship"]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["310974\/2013-5 and 477203\/2012-4"],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NUMEC\/USP","award":["Project MaCLinC\/USP"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2015,3]]},"abstract":"Abstract<\/jats:title>We give a polynomial time randomized algorithm that, on receiving as input a pair (H, G<\/jats:italic>) of n<\/jats:italic>\u2010vertex graphs, searches for an embedding of H<\/jats:italic> into G<\/jats:italic>. If H<\/jats:italic> has bounded maximum degree and G<\/jats:italic> is suitably dense and pseudorandom, then the algorithm succeeds with high probability. Our algorithm proves that, for every integer and a large enough constant C<\/jats:italic> = C<\/jats:italic>d<\/jats:italic><\/jats:sub>, as , asymptotically almost all graphs with n<\/jats:italic> vertices and at least edges contain as subgraphs all graphs with n<\/jats:italic> vertices and maximum degree at most d<\/jats:italic>. \u00a9 2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014<\/jats:p>","DOI":"10.1002\/rsa.20545","type":"journal-article","created":{"date-parts":[[2014,5,22]],"date-time":"2014-05-22T16:25:43Z","timestamp":1400775943000},"page":"274-299","source":"Crossref","is-referenced-by-count":7,"title":["An improved upper bound on the density of universal random graphs"],"prefix":"10.1002","volume":"46","author":[{"suffix":"Jr.","given":"Domingos","family":"Dellamonica","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science Emory University Atlanta Georgia 30322"}]},{"given":"Yoshiharu","family":"Kohayakawa","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science Emory University Atlanta Georgia 30322"},{"name":"Instituto de Matem\u00e1tica e Estat\u00edstica Universidade de S\u00e3o Paulo Rua do Mat\u00e3o 1010 05508\u2010090 S\u00e3o Paulo Brazil"}]},{"given":"Vojt\u011bch","family":"R\u00f6dl","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science Emory University Atlanta Georgia 30322"}]},{"given":"Andrzej","family":"Ruci\u0144ski","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science Emory University Atlanta Georgia 30322"},{"name":"Department of Discrete Mathematics Adam Mickiewicz University 61\u2010614 Pozna\u0144 Poland"}]}],"member":"311","published-online":{"date-parts":[[2014,5,22]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20143"},{"key":"e_1_2_8_3_1","first-page":"373","volume-title":"Proceedings of the Nineteenth Annual ACM\u2010SIAM Symposium on Discrete Algorithms","author":"Alon N.","year":"2008"},{"key":"e_1_2_8_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892007"},{"key":"e_1_2_8_5_1","first-page":"170","volume-title":"Approximation, randomization, and combinatorial optimization (Berkeley, CA, 2001), Lecture Notes in Computer Science Vol. 2129","author":"Alon N.","year":"2001"},{"key":"e_1_2_8_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2182-z"},{"key":"e_1_2_8_7_1","first-page":"53","volume-title":"43st Annual Symposium on Foundations of Computer Science (Vancouver, BC, 2002)","author":"Alstrup S.","year":"2002"},{"issue":"1","key":"e_1_2_8_8_1","doi-asserted-by":"crossref","first-page":"9","DOI":"10.37236\/278","article-title":"Large bounded degree trees in expanding graphs","volume":"17","author":"Balogh J.","year":"2010","journal-title":"Electron J Combin"},{"key":"e_1_2_8_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402014"},{"key":"e_1_2_8_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20337"},{"key":"e_1_2_8_11_1","first-page":"741","volume-title":"Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999)","author":"Capalbo M. R.","year":"1999"},{"issue":"1","key":"e_1_2_8_12_1","doi-asserted-by":"crossref","first-page":"14","DOI":"10.37236\/851","article-title":"An algorithmic Friedman\u2010Pippenger theorem on tree embeddings and applications","volume":"15","author":"Dellamonica D.","year":"2008","journal-title":"Electron J Combin"},{"key":"e_1_2_8_13_1","first-page":"782","volume-title":"Proceedings of the Nineteenth Annual ACM\u2010SIAM Symposium on Discrete Algorithms","author":"Dellamonica D.","year":"2008"},{"key":"e_1_2_8_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29344-3_20"},{"key":"e_1_2_8_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/10079882X"},{"key":"e_1_2_8_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20121"},{"key":"e_1_2_8_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010209"},{"key":"e_1_2_8_18_1","volume-title":"Random graphs, Wiley\u2010Interscience Series in Discrete Mathematics and Optimization","author":"Janson S.","year":"2000"},{"key":"e_1_2_8_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771528"},{"key":"e_1_2_8_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20224"},{"key":"e_1_2_8_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008619"},{"key":"e_1_2_8_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12788-9_6"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20545","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20545","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T17:06:56Z","timestamp":1693674416000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20545"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,22]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["10.1002\/rsa.20545"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20545","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,22]]}}}