Spanning universality in random graphs

A graph is said to be $\mathcal{H}(n,\mathrm{\Delta })$-universal if it contains every graph on $n$ vertices with maximum degree at most $\mathrm{\Delta }$. Using a `matching-based’ embedding technique introduced by Alon and F"uredi, Dellamonica, Kohayakawa, R"odl and Ruci'nski showed that the random graph $G_{n,p}$ is asymptotically almost surely $\mathcal{H}(n,\mathrm{\Delta })$-universal for $p=\tilde{\mathrm{\Omega }}(n^{-1\mathrm{/}\mathrm{\Delta }})$ - a threshold for the property that every subset of $\mathrm{\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 $\mathrm{\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)$-universalfor$p = \tilde \Omega(n^{- 1/(\Delta-1/2)})$.