An improved upper bound on the density of universal random graphs2. Issue 2 (22nd May 2014) - Dellamonica, Domingos; Kohayakawa, Yoshiharu; Rödl, Vojtěch; Ruciński, Andrzej
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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh3734f1bb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />d≥3</alternatives> and a large enough constant C = Cd, as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh3734f19s" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n→∞</alternatives>, asymptotically almost all graphs with n vertices and at least <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh3734f187" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Cn2−1/dlog1/dn</alternatives> edges contain as subgraphs all graphs with n vertices and maximum degree at most d. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014