Universality of random graphs and rainbow embedding

In this paper we show how to use simple partitioning lemmas in order to embed spanning graphs in a typical member of G ( n , p ) . Let the maximum density of a graph H be the maximum average degree of all the subgraphs of H . First, we show that for p = ω ( Δ 12n − 1 / 2 dlog 3 n ) , a graph G ∼ G ( n , p ) w.h.p. contains copies of all spanning graphs H with maximum degree at most Δ and maximum density at most d . For d < Δ / 2 , this improves a result of Dellamonica, Kohayakawa, Rödl and Rucińcki. Next, we show that if we additionally restrict the spanning graphs to have girth at least 7 then the random graph contains w.h.p. all such graphs for p = ω ( Δ 12n − 1 / dlog 3 n ) . In particular, if p = ω ( Δ 12n − 1 / 2log 3 n ) , the random graph therefore contains w.h.p. every spanning tree with maximum degree bounded by Δ. This improves a result of Johannsen, Krivelevich and Samotij. Finally, in the same spirit, we show that for any spanning graph H with constant maximum degree, and for suitable p , if we randomly color the edges of a graph G ∼ G ( n , p ) with ( 1 + o ( 1 ) ) | E ( H ) | colors, then w.h.p. there exists a rainbow copy of H in G (that is, a copy of H with all edges colored with distinct colors). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 546–564, 2016