Spanning universality in random graphs. Issue 4 (18th October 2018) - Ferber, Asaf; Nenadov, Rajko
Abstract: 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 graph G n, p is 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 that G n, p is almost surely H ( n, Δ ) ‐universal for p = Ω ( n − 1 / ( Δ − 0.5 ) log 3 n ) .