Premium
Almost‐spanning universality in random graphs
Author(s) -
Conlon David,
Ferber Asaf,
Nenadov Rajko,
Škorić Nemanja
Publication year - 2017
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.20661
Subject(s) - struct , universality (dynamical systems) , random graph , combinatorics , mathematics , random regular graph , discrete mathematics , graph , line graph , computer science , physics , pathwidth , quantum mechanics , programming language
A graph G is said to be ℋ ( n , Δ ) ‐universal if it contains every graph on at most n vertices with maximum degree at most Δ. It is known that for any ε > 0 and any natural number Δ there exists c > 0 such that the random graph G ( n, p ) is asymptotically almost surely ℋ ( ( 1 − ε ) n , Δ ) ‐universal for p ≥ c ( log n / n ) 1 / Δ. Bypassing this natural boundary, we show that for Δ ≥ 3 the same conclusion holds when p ≫ n − 1 Δ − 1log 5 n . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 380–393, 2017