Universality for bounded degree spanning trees in randomly perturbed graphs. Issue 4 (7th April 2019)

• Record Type: Journal Article
• Authors: Böttcher, Julia; Han, Jie; Kohayakawa, Yoshiharu; Montgomery, Richard; Parczyk, Olaf; Person, Yury
• Is Part Of: Random structures & algorithms. Volume 55:Issue 4(2019)
• Page Start: 854
• Page End: 864
• Publication Date: 2019-04-07
• Subjects: perturbed graphs -- random graphs -- spanning trees -- universality; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20850
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph G α on n vertices with δ ( G α ) ≥ αn for α > 0 and we add to it the binomial random graph G ( n, C / n ), then with high probability the graph G α ∪ G ( n, C / n ) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ.