An improved upper bound on the density of universal random graphs2. Issue 2 (22nd May 2014) - Dellamonica, Domingos
Abstract 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 d≥3 and a large enough constant C = Cd, as n→∞, asymptotically almost all graphs with n vertices and at least Cn2−1/dlog1/dn edges contain as subgraphs all graphs with n vertices and maximum degree at most d. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014