Premium
An improved upper bound on the density of universal random graphs
Author(s) -
Dellamonica Domingos,
Kohayakawa Yoshiharu,
Rödl Vojtěch,
Ruciński Andrzej
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20545
Subject(s) - combinatorics , mathematics , pseudorandom number generator , bounded function , degree (music) , discrete mathematics , random graph , embedding , upper and lower bounds , vertex (graph theory) , random regular graph , randomized algorithm , chordal graph , graph , 1 planar graph , computer science , algorithm , physics , mathematical analysis , artificial intelligence , acoustics
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 = C d , as n → ∞ , asymptotically almost all graphs with n vertices and at least C n 2 − 1 / dlog 1 / d n edges contain as subgraphs all graphs with n vertices and maximum degree at most d . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014