An improved upper bound on the density of universal random graphs

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.

NeuroCineMat
Featuring this week:
Newsletter

Stay informed on our latest news!



Previous issues

Podcast A Matemática do Cérebro
Podcast A Matemática do Cérebro
NeuroMat Brachial Plexus Injury Initiative
Logo of the NeuroMat Brachial Plexus Injury Initiative
Neuroscience Experiments System
Logo of the Neuroscience Experiments System
NeuroMat Parkinson Network
Logo of the NeuroMat Parkinson Network
NeuroMat's scientific-dissemination blog
Logo of the NeuroMat's scientific-dissemination blog