Almost‐spanning universality in random graphs1. Issue 3 (28th April 2016)

• Record Type: Journal Article
• Authors: Conlon, David; Ferber, Asaf; Nenadov, Rajko; Škorić, Nemanja
• Is Part Of: Random structures & algorithms. Volume 50:Issue 3(2017)
• Page Start: 380
• Page End: 393
• Publication Date: 2016-04-28
• Subjects: bounded degree graphs -- random graphs -- universality; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20661
• Languages: English
• ISSNs: 1042-9832

Abstract

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