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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom