Spanning universality in random graphs. Issue 4 (18th October 2018)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Nenadov, Rajko
• Is Part Of: Random structures & algorithms. Volume 53:Issue 4(2018)
• Page Start: 604
• Page End: 637
• Publication Date: 2018-10-18
• Subjects: Random graphs -- spanning subgraphs -- universality; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20816
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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 graph G n, p is 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 that G n, p is almost surely H ( n, Δ ) ‐universal for p = Ω ( n − 1 / ( Δ − 0.5 ) log 3 n ) .