Premium
Spanning universality in random graphs
Author(s) -
Ferber Asaf,
Nenadov Rajko
Publication year - 2018
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.20816
Subject(s) - combinatorics , mathematics , random graph , random regular graph , embedding , discrete mathematics , factor critical graph , distance hereditary graph , line graph , graph , pathwidth , computer science , voltage graph , artificial intelligence
A graph is said to be H ( n , Δ ) ‐universal if it contains every graph with n vertices and maximum degree at most Δ as a subgraph. Dellamonica, Kohayakawa, Rödl and Ruciński used a “matching‐based” embedding technique introduced by Alon and Füredi to show that the random graphG n , pis asymptotically almost surely H ( n , Δ ) ‐universal for p = Ω ( ( log n / n ) 1 / Δ ) , a threshold for the property that every subset of Δ vertices has a common neighbor. This bound has become a benchmark in the field and many subsequent results on embedding spanning graphs of maximum degree Δ in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing thatG n , pis almost surely H ( n , Δ ) ‐universal for p = Ω ( n − 1 / ( Δ − 0.5 )log 3 n ) .