An improved upper bound on the density of universal random graphs
From MaRDI portal
Publication:4982616
DOI10.1002/rsa.20545zbMath1309.05160OpenAlexW1967358236WikidataQ101496253 ScholiaQ101496253MaRDI QIDQ4982616
Andrzej Ruciński, Domingos jun. Dellamonica, Yoshiharu Kohayakawa, Vojtěch Rödl
Publication date: 9 April 2015
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20545
Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Density (toughness, etc.) (05C42)
Related Items
2-universality in randomly perturbed graphs ⋮ Spanning structures and universality in sparse hypergraphs ⋮ Sparse multipartite graphs as partition universal for graphs with bounded degree ⋮ Almost‐spanning universality in random graphs ⋮ On universal hypergraphs ⋮ Optimal threshold for a random graph to be 2-universal
Cites Work
- Embedding nearly-spanning bounded degree trees
- An algorithmic Friedman-Pippenger theorem on tree embeddings and applications
- Probabilistic methods for algorithmic discrete mathematics
- Upper tails for subgraph counts in random graphs
- Large bounded degree trees in expanding graphs
- An Improved Upper Bound on the Density of Universal Random Graphs
- Universality of Random Graphs
- Explicit sparse almost-universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$
- A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
- Factors in random graphs
- Universal Graphs for Bounded-Degree Trees and Planar Graphs
- Poisson approximation for large deviations
- Sparse universal graphs for bounded‐degree graphs
- Almost universal graphs
