| Texto completo | |
| Autor(es): |
Dellamonica, Jr., Domingos
[1]
;
Kohayakawa, Yoshiharu
[2]
;
Roedl, Vojtech
[1]
;
Rucinski, Andrzej
[1, 3]
Número total de Autores: 4
|
| Afiliação do(s) autor(es): | [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
Número total de Afiliações: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 26, n. 1, p. 353-374, 2012. |
| Citações Web of Science: | 7 |
| Resumo | |
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) | |
| Processo FAPESP: | 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas |
| Beneficiário: | Yoshiharu Kohayakawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Programa PRONEX - Temático |