An improved upper bound on the density of universal random graphs
We give a polynomial time randomized algorithm that, on receiving as input a pair (H, G) of n-vertex graphs, searches for an embedding of H into G. If H has bounded maximum degree and G 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 = Cd, as , asymptotically almost all graphs with n vertices and at least edges contain as subgraphs all graphs with n vertices and maximum degree at most d.  2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014
universality random graphs embeddings spanning subgraphs