Spanning universality in random graphs

Abstract

A graph is said to be $\mathcal{H}(n,\Delta )$-universal if it contains every graph on $n$ vertices with maximum degree at most $\Delta$. Using a `matching-based' embedding technique introduced by Alon and Füredi, Dellamonica, Kohayakawa, Rödl and Ruciński showed that the random graph $G_{n,p}$ is asymptotically almost surely $\mathcal{H}(n,\Delta )$-universal for $p=\tilde{\Omega }(n^{-1/\Delta })$ - a threshold for the property that every subset of $\Delta$ vertices has a common neighbour. This bound has become a benchmark in the field and many subsequent results on embedding spanning structures of maximum degree $\Delta$ in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing that $G_{n,p}$ is almost surely $\mathcal{H}(n,\Delta )$-universal for $p=\tilde{\Omega }(n^{-1/(\Delta -1/2)})$.