Premium
Universality of random graphs and rainbow embedding
Author(s) -
Ferber Asaf,
Nenadov Rajko,
Peter Ueli
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20596
Subject(s) - combinatorics , rainbow , mathematics , random graph , spanning tree , discrete mathematics , random regular graph , embedding , bounded function , degree (music) , graph , 1 planar graph , chordal graph , computer science , physics , mathematical analysis , quantum mechanics , artificial intelligence , acoustics
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