UNIVERSALITY OF RANDOM GRAPHS
| Contribuinte(s) |
UNIVERSIDADE DE SÃO PAULO |
|---|---|
| Data(s) |
06/11/2013
06/11/2013
2012
|
| 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. CAPES NSF [DMS080070] Charles University, Prague FAPESP [FAPESP 2003/09925-5] CNPq [308509/2007-2, 485671/2007-7, 486124/2007-0] Polish Ministry of Higher Education [N201036 32/2546] |
| Identificador |
SIAM JOURNAL ON DISCRETE MATHEMATICS, PHILADELPHIA, v. 26, n. 1, pp. 353-374, DEC 3, 2012 0895-4801 http://www.producao.usp.br/handle/BDPI/41985 10.1137/10079882X |
| Idioma(s) |
eng |
| Publicador |
SIAM PUBLICATIONS PHILADELPHIA |
| Relação |
SIAM JOURNAL ON DISCRETE MATHEMATICS |
| Direitos |
restrictedAccess Copyright SIAM PUBLICATIONS |
| Palavras-Chave | #RANDOM GRAPHS #UNIVERSALITY #BOUNDED DEGREE GRAPHS #GRAPH EMBEDDING #BLOW-UP LEMMA #SPANNING SUBGRAPHS #MATHEMATICS, APPLIED |
| Tipo |
article original article publishedVersion |
