An improved upper bound on the density of universal random graphs
Domingos Dellamonica, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński · Random Structures and Algorithms · 2014
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 and a large enough constant C = C d , 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