2013/11/27 by Ferber, Asaf, Nenadov, Rajko, Peter, Ueli
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1311.7063
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=ω(Δ12 n-1/2dlog3n), 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