UNIVERSALITY OF RANDOM GRAPHS

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.CAPESNSF [DMS080070]Charles University, PragueFAPESP [FAPESP 2003/09925-5]CNPq [308509/2007-2, 485671/2007-7, 486124/2007-0]Polish Ministry of Higher Education [N201036 32/2546