Spanning universality in random graphs

A graph is said to be H ( n , Δ ) ‐universal if it contains every graph with n vertices and maximum degree at most Δ as a subgraph. Dellamonica, Kohayakawa, Rödl and Ruciński used a “matching‐based” embedding technique introduced by Alon and Füredi to show that the random graphG n , pis asymptotically almost surely H ( n , Δ ) ‐universal for p = Ω ( ( log n / n ) 1 / Δ ) , a threshold for the property that every subset of Δ vertices has a common neighbor. This bound has become a benchmark in the field and many subsequent results on embedding spanning graphs of maximum degree Δ in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing thatG n , pis almost surely H ( n , Δ ) ‐universal for p = Ω ( n − 1 / ( Δ − 0.5 )log 3 n ) .