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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom