Almost-spanning universality in random graphs

Abstract

A graph $G$ is said to be $\mathcal{H}(n,\hat{I}”)$-universal if it contains every graph on $n$ vertices with maximum degree at most $\hat{I}”$. It is known that for any $\epsilon >0$ and any natural number $\hat{I}”$ there exists $c>0$ such that the random graph $G(n,p)$ is asymptotically almost surely $\mathcal{H}((1-\epsilon )n,\hat{I}”)$-universal for $p\ge c(\log n/n{)}^{1/\hat{I}”}$. Bypassing this natural boundary, we show that for $\hat{I}”\ge 3$ the same conclusion holds when $p=\ddot{I}‰\left(n^{-\frac{1}{\hat{I}”-1}}{\log }^{5}n\right)$.