Advertisement
Published in:
2012 | OriginalPaper | Chapter
An Improved Upper Bound on the Density of Universal Random Graphs
Authors : Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 suitable constant
C
=
C
d
, as
n
→ ∞, asymptotically almost all graphs with
n
vertices and
$\lfloor Cn^{2-1/d}\log^{1/d}n\rfloor$
edges contain as subgraphs all graphs with
n
vertices and maximum degree at most
d
.