An improved upper bound on the density of universal random graphs
Sep 26, 2016
Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Vojtěch Rödl and Andrzej Ruciński
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/d log1/d n edges contain as subgraphs all graphs with n vertices and maximum degree at most d.
The whole paper is available here.
Share on Facebook
