| Full text | |
| Author(s): |
Dellamonica, Jr., Domingos
[1]
;
Kohayakawa, Yoshiharu
[2]
;
Roedl, Vojtech
[1]
;
Rucinski, Andrzej
[1, 3]
Total Authors: 4
|
| Affiliation: | [1] Emory Clin, Dept Math & Comp Sci, Atlanta, GA 30322 - USA
[2] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
[3] Adam Mickiewicz Univ, Poznan - Poland
Total Affiliations: 3
|
| Document type: | Journal article |
| Source: | SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 26, n. 1, p. 353-374, 2012. |
| Web of Science Citations: | 7 |
| Abstract | |
We prove that asymptotically (as n -> infinity) almost all graphs with n vertices and C(d)n(2-1/2d) log(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. (AU) | |
| FAPESP's process: | 03/09925-5 - Foundations of computer science: combinatory algorithms and discrete structures |
| Grantee: | Yoshiharu Kohayakawa |
| Support Opportunities: | PRONEX Research - Thematic Grants |