Almost‐spanning universality in random graphs1. Issue 3 (28th April 2016) - Conlon, David; Ferber, Asaf; Nenadov, Rajko; Škorić, Nemanja
Abstract: 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 Δ − 1 log 5 n . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 380–393, 2017