An improved upper bound on the density of universal random graphs

DOI10.1007/978-3-642-29344-3_20MaRDI QIDQ2894468zbMATH OpenOpenAlexWikidataFDO

Authors Domingos Dellamonica, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński

Publication date 29 June 2012

Published in LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-29344-3_20

zbMATH Keywords

bounded maximum degreedensitypolynomail time randomized algorithmpseudorandom

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An improved upper bound on the density of universal random graphs
• Universality of random graphs
• Embedding large graphs into a random graph
• Universality of random graphs and rainbow embedding
• Spanning universality in random graphs

Cited in

(8)

• Intersections of randomly embedded sparse graphs are Poisson
• Improved replica bounds for the independence ratio of random regular graphs
• Universality of random graphs
• Almost-spanning universality in random graphs (extended abstract)
• An improved upper bound on the density of universal random graphs
• Optimal threshold for a random graph to be 2-universal
• Finding any given 2‐factor in sparse pseudorandom graphs efficiently
• Powers of Hamilton cycles in pseudorandom graphs

This page was built for publication: An improved upper bound on the density of universal random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2894468)