Universality of random graphs and rainbow embedding. Issue 3 (7th July 2015)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Nenadov, Rajko; Peter, Ueli
• Is Part Of: Random structures & algorithms. Volume 48:Issue 3(2016)
• Page Start: 546
• Page End: 564
• Publication Date: 2015-07-07
• Subjects: random graphs -- embeddings -- universality; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20596
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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 / 2 d log 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 = ω ( Δ 12 n − 1 / d log 3 n ) . In particular, if p = ω ( Δ 12 n − 1 / 2 log 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