Universality for bounded degree spanning trees in randomly perturbed graphs

Abstract

We solve a problem of Krivelevich, Kwan and Sudakov [SIAM Journal on Discrete Mathematics 31 (2017), 155-171] 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_{\alpha }$ on $n$ vertices with $\delta (G_{\alpha })\ge \alpha n$ for $\alpha >0$ and we add to it the binomial random graph $G(n,C/n)$, then with high probability the graph $G_{\alpha }\cup G(n,C/n)$ contains copies of all spanning trees with maximum degree at most $\Delta$ simultaneously, where $C$ depends only on $\alpha$ and $\Delta$.

12 pages, accepted for publication in Random Structures & Algorithms