Almost-spanning universality in random graphs
Preprint
Abstract
A graph $G$ is said to be $\mathcal H(n,\Delta)$-universal if it contains every graph on $n$ vertices with maximum degree at most $\Delta$. It is known that for any $\varepsilon > 0$ and any natural number $\Delta$ there exists $c > 0$ such that the random graph $G(n,p)$ is asymptotically almost surely $\mathcal H((1-\varepsilon)n,\Delta)$-universal for $p \geq c (\log n/n)^{1/\Delta}$. Bypassing this natural boundary, we show that for $\Delta \geq 3$ the same conclusion holds when $p = \omega\left(n^{-\frac{1}{\Delta-1}}\log^5 n\right)$.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- An improved upper bound on the density of universal random graphsRandom Structures & Algorithms, 2014
- Almost Spanning Subgraphs of Random Graphs After Adversarial Edge RemovalCombinatorics, Probability and Computing, 2013
- Sparse partition universal graphs for graphs of bounded degreeAdvances in Mathematics, 2011
- Local resilience of almost spanning trees in random graphsRandom Structures & Algorithms, 2010
- Sparse universal graphs for bounded‐degree graphsRandom Structures & Algorithms, 2006
- Sparse universal graphsJournal of Computational and Applied Mathematics, 2002
- Hall's theorem for hypergraphsJournal of Graph Theory, 2000
- Universal Graphs for Bounded-Degree Trees and Planar GraphsSIAM Journal on Discrete Mathematics, 1989
- On Universal Graphs for Spanning TreesJournal of the London Mathematical Society, 1983
- On size Ramsey number of paths, trees, and circuits. IJournal of Graph Theory, 1983